	.data
Title:	.asciiz "\n
             2444  4444 347 8444444  0440445   
             2404  4444 747 04   340 4477 77
             74 4434 44 74  5480887    77344                         
             74  447 44 747 24       44   447                        
              7   7  7   7   7        73577                          
                                                                     
                                                                      
               044447  24    47  4484442  344447   044447            
             744   04  44    44  44      044  54  442  08            
             44        44444440  447520   738807   728807            
             740   44  44    44  40      58   744 02   348           
               24440   74    47  4808444  044883   444887 
															
              5                                                     
             444                                                      
            30407              47                                     
             240              244                                     
           7044487            444                                     
         74442704447        77044777                                  
          0037 7752        4444444447          74                     
           0228573         3055232207         44447                   
           8480002          00000227         744444        7757       
          702553357         44444847          7007        744442      
            77777            777777           7440        444444440   
           7444087           808007         34444443      44007  34   
           7800227          7488085         77777577      74440       
           7400207           480007           8800         4404447    
           7022527           000007           4444        844444444   
           7804005           444443          74444        44444445    
           4000208          2408844          74444        2000220     
           0222520          5000084          74444       700000287    
         758000004877    7788000084427     7708844477   74000000447   
       732222000222257   35222222533777   722222222027  77335555557
		
       W/S/A/D: move cursor   Enter/Esc: Select/Deselect    Q: quit
			
                         [Press Enter to Continue]
"
prompt: .asciiz "Only runs with -mapped_io flag.\nPlease type 6 input lines:\n"
quit: .asciiz "Thank you for playing MIPS Chess"
nl:	.asciiz "\n"
row: .asciiz "  +-------+-------+-------+-------+-------+-------+-------+-------+\n"
bottom: .asciiz "      a       b       c       d       e       f       g       h  \n"
bar: .asciiz "|"
empty: .asciiz "       "
wempty: .asciiz "       "
bempty: .asciiz ":::::::"

space: .asciiz " "
dot: .asciiz ":"
clear: .asciiz "\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n"
buff: .word 0
sec: .word 0
off: .word 0

bpawn1w: .asciiz "       "
bpawn2w: .asciiz "  (#)  "
bpawn3w: .asciiz "  /#\  "
bpawn4w: .asciiz " (###) "
bknig1w: .asciiz "  _,/| "
bknig2w: .asciiz " /_#)\ "
bknig3w: .asciiz "  /#\\ "
bknig4w: .asciiz " (###) "
bbish1w: .asciiz "  /\\  "
bbish2w: .asciiz "  \#/  "
bbish3w: .asciiz "  (#)  "
bbish4w: .asciiz " (###) "
brook1w: .asciiz " [_|_] "
brook2w: .asciiz "  [#]  "
brook3w: .asciiz "  [#]  "
brook4w: .asciiz " (###) "
bquee1w: .asciiz "  \*/  "
bquee2w: .asciiz "  (#)  "
bquee3w: .asciiz "  /#\  "
bquee4w: .asciiz " (###) "
bking1w: .asciiz "  \+/  "
bking2w: .asciiz "  {#}  "
bking3w: .asciiz "  {#}  "
bking4w: .asciiz " (###) "

wpawn1w: .asciiz "       "
wpawn2w: .asciiz "  ( )  "
wpawn3w: .asciiz "  / \  "
wpawn4w: .asciiz " (   ) "
wknig1w: .asciiz "  _,/| "
wknig2w: .asciiz " /_ )\ "
wknig3w: .asciiz "  / \\ "
wknig4w: .asciiz " (   ) "
wbish1w: .asciiz "  /\\  "
wbish2w: .asciiz "  \ /  "
wbish3w: .asciiz "  ( )  "
wbish4w: .asciiz " (   ) "
wrook1w: .asciiz " [_|_] "
wrook2w: .asciiz "  [ ]  "
wrook3w: .asciiz "  [ ]  "
wrook4w: .asciiz " (   ) "
wquee1w: .asciiz "  \*/  "
wquee2w: .asciiz "  ( )  "
wquee3w: .asciiz "  / \  "
wquee4w: .asciiz " (   ) "
wking1w: .asciiz "  \+/  "
wking2w: .asciiz "  { }  "
wking3w: .asciiz "  { }  "
wking4w: .asciiz " (   ) "

bpawn1b: .asciiz ":::::::"
bpawn2b: .asciiz "::(#)::"
bpawn3b: .asciiz "::/#\::"
bpawn4b: .asciiz ":(###):"
bknig1b: .asciiz "::_,/|:"
bknig2b: .asciiz ":/_#)\:"
bknig3b: .asciiz "::/#\\:"
bknig4b: .asciiz ":(###):"
bbish1b: .asciiz "::/\\::"
bbish2b: .asciiz "::\#/::"
bbish3b: .asciiz "::(#)::"
bbish4b: .asciiz ":(###):"
brook1b: .asciiz ":[_|_]:"
brook2b: .asciiz "::[#]::"
brook3b: .asciiz "::[#]::"
brook4b: .asciiz ":(###):"
bquee1b: .asciiz "::\*/::"
bquee2b: .asciiz "::(#)::"
bquee3b: .asciiz "::/#\::"
bquee4b: .asciiz ":(###):"
bking1b: .asciiz "::\+/::"
bking2b: .asciiz "::{#}::"
bking3b: .asciiz "::{#}::"
bking4b: .asciiz ":(###):"

wpawn1b: .asciiz ":::::::"
wpawn2b: .asciiz "::( )::"
wpawn3b: .asciiz "::/ \::"
wpawn4b: .asciiz ":(   ):"
wknig1b: .asciiz "::_,/|:"
wknig2b: .asciiz ":/_ )\:"
wknig3b: .asciiz "::/ \\:"
wknig4b: .asciiz ":(   ):"
wbish1b: .asciiz "::/\\::"
wbish2b: .asciiz "::\ /::"
wbish3b: .asciiz "::( )::"
wbish4b: .asciiz ":(   ):"
wrook1b: .asciiz ":[_|_]:"
wrook2b: .asciiz "::[ ]::"
wrook3b: .asciiz "::[ ]::"
wrook4b: .asciiz ":(   ):"
wquee1b: .asciiz "::\*/::"
wquee2b: .asciiz "::( )::"
wquee3b: .asciiz "::/ \::"
wquee4b: .asciiz ":(   ):"
wking1b: .asciiz "::\+/::"
wking2b: .asciiz "::{ }::"
wking3b: .asciiz "::{ }::"
wking4b: .asciiz ":(   ):"

A:		.asciiz "A"
B:		.asciiz "B"
C:		.asciiz "C"
D:		.asciiz "D"
E:		.asciiz "E"
F:		.asciiz "F"
G:		.asciiz "G"
H:		.asciiz "H"

uparr: .asciiz "^"
leftarr: .asciiz "<"
select: .asciiz "Selected: "
hitenter: .asciiz "Hit enter to select piece."
selectempty: .asciiz "Cannot select empty space."
invalid:	.asciiz "Invalid move.\n"
moveto:	.asciiz "Move to: "
wturn:	.asciiz "White's turn. "
bturn:	.asciiz "Black's turn. "
cma:	.asciiz ","
arrow:	.asciiz "->"
error:	.word 0
turn:	.word 1
# Create the chessboard array (see wiki)
newboard: .word 1110795044, 286331153, 0, 0, 0, 0, -1717986919, -893523028
board: .word 1110795044, 286331153, 0, 0, 0, 0, -1717986919, -893523028
nwcap: .word 0
nbcap: .word 0
wcaptured: .word 0,0,0,0,0,0,0,0
bcaptured: .word 0,0,0,0,0,0,0,0

# The previous and current location after an AI movement
aisrcx: .word 0
aisrcy: .word 0
aidestx: .word 0
aidesty: .word 0
aiinform: .asciiz "Black player is pondering...\n"
aidecision: .asciiz "Black player has decided: "

# Boolean value for playing against AI or not
aiopponent:	.word 1

# Menu options
menuhead: .asciiz "MIPS Chess Main Menu: Would You Like To Play A Game?\n\n"
menuai: .asciiz "1: One Player - Play Against AI\n"
menuop: .asciiz "2: Two Player - Play Against Human\n"
menuq: .asciiz "0: Quit\n"
menuprompt: .asciiz "Selection: "

# Victory Prompts
informcheckmate: .asciiz "Checkmate!!\n"
whitevictory: .asciiz "
                                            saa,       saa,                     
                         dQQ(   dQQQ(   dQQ;dQW;       dWQ;  dQQ(               
                          dQQ(  dQQQ(  dQQ( dQQ;saaa,  saa, smQQwaa,  saaaaa,   
                          dQQ( dQ( dQ( dQQ( dQQQP?$WQ; dWQ; *$QQP??`smWY???$Qw, 
                           dQQ(dQ; dQ(dQQ(  dQQ;  dQQ; dQQ;  dQQ;   dQQQQQQQQQ; 
                           ?$QQW;   dQQQP`  dQQ(  dQQ; dQQ;  dQQ;   dQQw,    s, 
            saaaaaaaaaaaaa, dQQQ;   dQQQ;   dQQ(  dQQ; dQQ;  ?$QQQQ; *?$QQQQQY` 
         samQWWwamWWQWQWQWP$;                                                   
        dwmWQQ;      smQQQw,*s,                                                 
       dw7s7saaaamWQWamQQQW;sm;                                                 
       ?$a,*$QaaaaaaaaamQPsmQP`                                                 
        dP?$(3QwaaaaamYsmWP`d;                                                  
        dw,dQQQP?????$WQwm; d(                                                  
        dQw,                d(                                                  
        dwaa,              dQ(                                                  
         saa,               d(                                                  
         *$aa,            sm;                                                   
             dQQWQQQQQQQWY`       saa,   saaa,   saa,dQQ(                       
             dQQQQQQQQP$;         *$Qw,  dWQW;  smWY`*??*                       
             dP???`    dw,         dQQ; smP?$w, dWW; dQQ( dQQwmQQQw, smQQQQQw,  
            smP$Qw,    dQ;         ?$Qw,3Q; dQ;smQP` dQQ( dQQY` dQQ; dQQwa, **  
            dQWP?`      d(          dQQwmP` ?$wmWQ;  dQQ( dQQ;  dQQ;  *???$Qw,  
           smP???`      dw,          dQWW;   dQWQ;   dQQ( dQQ;  dQQ; dwaaamQQ;  
           dWP??`       dQ;          ????`   *???`   ???` ???`  ???`  *?????`   
          <mQQW;        ?$;                                                     
         dQw7??`         d;                                                     
      samQQP?$w,          s,                                                    
    smWWQQP?$Q;           dQQwa,                                                
   smWQQQP$Qw,            dQQQY$;                                               
   dWQQQQWQW;             dQ;d; d(                                              
   dQQP?$; *$waaaaaaaaaamQ(smP` d(                                              
   dQQ;  dwa,  *???????`  dY` smQ;                                              
   dQwmw,  *?$QwaaaaaaamQP` smW;d(                                              
   dQQQY`dwa,           samY`   d(                                              
QQQQQQP`   *?$QQwaaamQQP??`     d(                                              
 dQQQQw,                      smQ(                                              
   ?$QQQw,                 samQY`                                               
        *$QQwaaaa,  saaamQP`                                                    
            *??????????`                                                        
"
blackvictory: .asciiz "
 _aaaaaac    )WQk                      )WQk                                     
 =QQD??9WQk  =QQk                      =QQk                                     
 =QQk  =QQk  =QQk  _wQQQQmc   _wQQQQmc =QQk _wQ@*                               
 )WQQQWQQmc  )WQk  -\aaawQQk =QQ@*  -! )WQmwW@*            s,                   
 =QQk   =QQk =QQk )WQ@??4WQk )WQk      =QQ@4Wmc          smWP$P?saa,            
 =QQmaaawQ@* =QQk =QQmaawWQk -9WQmaawk =QQk -9Qmc     dPsm;d;*s,**dP?sa,        
 -???????*   -??*  -???*-??*   -????*  -??*   -??*    d;*$wm( ?$;d(<m; dwa,     
                                                      dwmP?`   *??s7smP` dQ;    
                                                    s7?`           dQ;smP?`dw,  
                                                  s7`              *??saamP??$; 
                                                 dP`  smP?`         ??$Q;saaa7s,
                                               sm;  sm;d;            dwmQY`<aamw
                                               d;  *?`*?*            saamQP?`  d
                                              dP`                     *??$QP???$
                                             dPsm;                    dP?$waaaam
                                            dPs7`                 s,   *?$;    d
                                          smPs7`      s,       samP`  ???$QP???$
                                        smYsmY`     smY?$waaamY?`    *??$Qwaaaam
                                     smP?`        s)?`   d;         ????$P????$Q
                                     d;s7`    s, d;     sm;         dQP$P??$wam;
                                     *sa,    dQ;dP`    sm;         saamQwaaaamY`
                                        *s,<mP???`    s7`          saam;   *$P` 
                    saa,                  *?`       smYs,         saamY????$P`  
 dQQ;   dQQQ;   dQQ;dWW;                           dP` d;         *?$Y` saam;   
  dQQ;  dQQQ;  dQQ; saa, saa,saaa,   saaaaa,     smP`smP`         ??$w7??`      
  dQQ( dQ( dQ( dQQ( dWQ; dWWQY?$WQ; dQWY???$;    d; smY`         *??$;          
   dQQ;dQ( dQ(3QQ(  dQQ; dQQ;  dQQ; ?$QQQwa,    dP`dQW;          ???$(          
   ?$QQQ(   dQQQP`  dQQ; dQQ;  dQQ; s,   dWQ;  sm;s7$;          samP$Qw,        
    dQQQ;   dQQQ;   dQQ; dQQ;  dQQ; *$QQQQQP`smW;  dQ;          samY$QWQ;       
                                             d;*s,             saamWQQP$Q;      
                                            dPs,???saaaaaaamY???smWQPsmY$w,     
                                           sm; *?saaaaaaaaaaamP??` *?sa7`dw,    
                                           d;                       ?`smY`d;    
                                          sm;                          sa7$Q;   
                                          d;                          *?smQP`   
                                          *$(                          dwmY`    
                                            ??s,                   saa7?`       
                                               ???saaaaaaaaaaaaamY??`           
"

# The current location x=column, y=row
locx: .word 0
locy: .word 7

# The selected location x=column, y=row
slocx: .word -1
slocy: .word -1

	.text
	.globl main
main:
li	$a0, 40000
li	$v0, 9
syscall
sw		$v0, buff

#
# Draw the splash screen and pause for enter
#
	jal		newline				# print out the title page
	la		$a0,Title
	jal		printstr
	li		$v0,5				# wait for user to hit return
	syscall
#
# End splash screen
#
	
#
# Menu
#
mainmenu:
	la		$a0, clear			# Clear the screen
	jal		printstr
	la		$a0,menuhead
	jal		printstr
	la		$a0,menuai
	jal		printstr
	la		$a0,menuop
	jal		printstr
	la		$a0,menuq
	jal		printstr
	jal		newline
	la		$a0,menuprompt
	jal		printstr
	li		$v0,5
	syscall
	blt		$v0,$zero,mainmenu
	bgt		$v0,3,mainmenu
	beq		$v0,$zero,terminate
	add		$t0,$zero,$zero
	seq		$t0,$v0,1
	sw		$t0,aiopponent
	la		$a0,newboard
	la		$a1,board
	jal		ai_copy_board
#
# End menu
#

#
# Draw the chess board
#
drawboard:
	jal		wrt_nl
	li 		$s2, 8
	li 		$s3, 0
board_row_loop:		# for (int s3 = 0; s3 < 8; s3++) :
	la 		$a0, row
	jal 	wrt_strz
		
	li		$s4, 4
	li		$s5, 0
board_piece_loop:	
	li		$a0, 8
	subu	$a0, $a0, $s3
	jal 	wrt_int	# draw row number
	
	la 		$a0, space
	jal 	wrt_strz
	
	
	li 		$s0, 8
	li 		$s1, 0
board_col_loop:		# for (int s1 = 0; s1 < 8; s1++) :
	
	la 		$a0, bar
	jal 	wrt_strz
	
drawchesspiece:
	move 	$a0, $s1
	move 	$a1, $s3
	move	$a2, $s5
	jal 	drawpiece			# draw the chess piece

donedrawchesspiece:

	addi 	$s1, $s1, 1
	
	bne 	$s1, $s0, board_col_loop	
endboard_col_loop:	# endfor;

	la 		$a0, bar
	jal 	wrt_strz
	la		$a0, space
	jal		wrt_strz
	lw		$t0, locy
	beq		$t0, $s3, draw_locy
	j		not_locy
	
draw_locy:
	la		$a0, leftarr
	jal		wrt_strz
	
not_locy:
	jal 	wrt_nl
	
	
	addi	$s5, $s5, 1
	bne		$s5, $s4, board_piece_loop
	
	addi 	$s3, $s3, 1
	bne 	$s3, $s2, board_row_loop
end_board_row_loop:	# endfor;

	la 		$a0, row
	jal 	wrt_strz
	
	la 		$a0, bottom
	jal 	wrt_strz				# draw column letter
	
	la		$a0, space
	jal		wrt_strz
	jal		wrt_strz
	
	lw		$s1, locx
	li		$s0, 0

	beq		$s1, $s0, draw_locx
	addi	$s1, $s1, -1
draw_locx_loop:
	la		$a0, space
	jal		wrt_strz
	jal		wrt_strz
	jal		wrt_strz
	jal		wrt_strz
	jal		wrt_strz
	jal		wrt_strz
	jal		wrt_strz
	jal		wrt_strz
	
	addi	$s0, $s0, 1	
	ble		$s0, $s1, draw_locx_loop
draw_locx:	
	la		$a0, space
	jal		wrt_strz
	la		$a0, uparr
	jal		wrt_strz
	jal		wrt_strz
	jal		wrt_strz
	jal		wrt_strz
	jal		wrt_strz
	jal		wrt_strz
	jal		wrt_strz
	
	jal		wrt_nl

checkmate:
	li		$a0,0
	la		$a1,board
	jal		ai_check_checkmate
	bne		$v0,$zero,wvictory
	li		$a0,1
	la		$a1,board
	jal		ai_check_checkmate
	bne		$v0,$zero,wvictory

	lw		$a0, turn
	beq		$a0, $zero, drawbturn
drawwturn:
	la		$a1,board
	li		$a0,1
	jal		ai_utility
	add		$a0,$zero,$v0
	li		$v0,1
	syscall
	jal		wrt_nl
	
	la		$a0, wturn
	jal		wrt_strz
	j		isselected
drawbturn:	
	la		$a1,board
	li		$a0,0
	jal		ai_utility
	add		$a0,$zero,$v0
	li		$v0,1
	syscall
	jal		wrt_nl
	
	la		$a0, bturn
	jal		wrt_strz
	
isselected:
	lw		$a0, slocx
	blt		$a0, $zero, notselected
	lw		$a1, slocy
	blt		$a0, $zero, notselected
	
#	jal		getpiece
#	beq		$v0, $zero, nopiece
	
	la		$a2,board
	jal		ai_gen_moves
	move	$a0,$v0
	add		$v0,$zero,1
	syscall
	jal		wrt_nl


	la		$a0, select
	jal		wrt_strz

	lw		$a0,slocx
	lw		$a1,slocy
	jal		printboardloc
	
	jal		wrt_nl
	la		$a0, moveto
	jal		wrt_strz
	
	lw		$a0, locx
	lw		$a1, locy
	jal		printboardloc
	
	j		finishdrawboard
notselected:
	la		$a0, hitenter
	jal		wrt_strz
	j		finishdrawboard
#nopiece:
#	la		$a0, selectempty
#	jal		wrt_strz
	
finishdrawboard:
	jal		wrt_nl
	lw		$a0, error
	beq		$a0, 1, invalidmove
	j		noerror
invalidmove:
	la		$a0, invalid
	jal		wrt_strz
noerror:
	sw		$zero, error
	
	jal		printbuff
#
# Finished drawing the chessboard
#

# Register usage:
#		s0		loop counter
#		t0		address of recv_ctrl
#		t1		address of recv_buffer
#		t2		address of trans_ctrl
#		t3		address of trans_buffer
#		t4, t5		temporaries
#		t6		char read from input
#		t7		1 => char in t6

	li 		$s0, 3		# loop counter


	li 		$t0, 0xffff0000	# recv ctrl
	li 		$t1, 0xffff0004	# recv buf
	li 		$t2, 0xffff0008	# trans ctrl
	li 		$t3, 0xffff000c	# trans buf

# First, read and echo 3 lines of input by polling the IO registers, not through
# interrupts:

	mtc0 	$0, $12				# Clear IE bit in Status reg to disable interrupts

l1:
	lw 		$t4, 0($t0)			# Wait for receiver ready
	and 	$t4, $t4, 1
	beq 	$t4, 0, l1

	lw 		$t6, 0($t1)			# Read character

l2:
	lw 		$t4, 0($t2)			# Wait for transmitter ready
	and 	$t4, $t4, 1
	beq 	$t4, 0, l2

	#sw 	$t6, 0($t3)			# Write character
	
	la		$a0, clear			# Clear the screen
	jal		printstr
	
	li		$s0, 100			# D is right
	beq		$t6, $s0, checkright
	
	li		$s0, 97
	beq		$t6, $s0, checkleft # A is left
	
	li		$s0, 119
	beq		$t6, $s0, checkup	# W is up
	
	li		$s0, 115
	beq		$t6, $s0, checkdown	# S is down
	
	li		$s0, 113			# q terminates the application
	beq		$t6, $s0, mainmenu
	
	li		$s0, 27
	beq		$t6, $s0, deselect	# esc deselects the current selection
	
	beq 	$t6, 0xa, enter		# Enter to select a piece
	
	j	drawboard				# Other keys will be ignored (to be modified)

	deselect:
		li		$a0, -1
		sw		$a0, slocx				# Reset selected location x
		sw		$a0, slocy				# Reset selected location y
		j		drawboard
		
	enter:								# Enter has been pressed
		lw		$s0, slocx
		blt		$s0, $zero, selectloc	# If slocx<0 then a selection has not been made yet
		lw		$s0, slocy
		blt		$s0, $zero, selectloc	# If slocy<0 then a selection has not been made yet
	
									# A selection has been made
		jal		checkmove			# Check if the move is valid from (slocx,slocy) => (locx, locy)
		j		drawboard			# And perform the move
		
	selectloc:						# A selection has not been made yet
		lw		$s0, locx
		sw		$s0, slocx			# Move locx -> slocx
		lw		$s0, locy
		sw		$s0, slocy			# Move locy -> slocy
		j		drawboard

	checkright:						# Right has been pressed
		lw		$s0, locx
		li		$s1, 6
		ble		$s0, $s1, right		# Check that locx+1 <= 7
		j		drawboard
	right:
		addi	$s0, $s0, 1			# Then locx++
		sw		$s0, locx
		j		drawboard

	checkleft:						# Left has been pressed
		lw		$s0, locx
		bgt		$s0, $zero, left	# Check that locx-1 > 0
		j		drawboard
	left:
		addi	$s0, $s0, -1		# Then locx--
		sw		$s0, locx
		j		drawboard

	checkup:						# Up has been pressed
		lw		$s0, locy
		bgt		$s0, $zero, up		# Check that locy-1 > 0
		j		drawboard			# Top-Left is our origin.
	up:								# Up corresponds to decrementing locy
		addi	$s0, $s0, -1
		sw		$s0, locy			# Then locy--
		j		drawboard

	checkdown:						# Down has been pressed
		lw		$s0, locy
		li		$s1, 6
		ble		$s0, $s1, down		# Check that locy+1 <= 7
		j		drawboard
	down:
		addi	$s0, $s0, 1			# Then locy++
		sw		$s0, locy
		
	# Loop program infinitely	
	j		drawboard	

	# Done echoing, so terminate program.
	li $v0 10
	syscall			# syscall 10 (exit)

	# Return from handler.
ret_handler:
	mfc0 $t4 $12		# Enable interrupts and mask in Status reg
	ori $t4 $t4 0xff01
	mtc0 $t4 $12

	eret			# return to interrupted instruction


exception:
	li $v0 4		# Non-interrupt exception
	la $a0 other_str	# Print message and ignore
	syscall
	b ret_handler

no_recv_ready:
	li $v0 4		# Receiver was not ready after interrupt
	la $a0 no_recv_str	# Print message and ignore
	syscall
	b ret_handler

bad_int:
	li $v0 4		# Interrupt was not from recv or trans
	la $a0 bad_int_str	# Print message and ignore
	syscall
	b ret_handler

no_trans_ready:
	li $v0 4		# Transmitter was not ready after interrupt
	la $a0 no_trans_str	# Print message and ignore
	syscall
	b ret_handler

############################################################################
#                          Victory Dances                                  #
############################################################################
bvitory:
	la	$a0,informcheckmate
	jal	printstr
	li	$v0,5
	syscall
	la	$a0,blackvictory
	jal	printstr
	li	$v0,5
	syscall
	j	mainmenu

wvictory:
	la	$a0,informcheckmate
	jal	printstr
	li	$v0,5
	syscall
	la	$a0,whitevictory
	jal	printstr
	li	$v0,5
	syscall
	j	mainmenu

#############################################################################
printint:						#	this routine makes it easier to print an integer
								#	though the same preparations must be made as before
		li		$v0, 1			#	prepare for system call
		syscall

		jr		$ra				#	return to caller

printstr:						#	this routine makes it easier to print strings
		li		$v0, 4			#	prepare for system call
		syscall

		jr		$ra				#	return to caller

newline:						#	this routine makes it easier to print "\n"
		li		$v0, 4			#	prepare for system call
		la		$a0, nl
		syscall

		jr		$ra				#	return to caller
		
mod:							#	calculates $a0 mod $a1
		divu	$a0, $a1
		mfhi	$v0

		jr		$ra
terminate:
		la		$a0, quit
		jal		printstr
		jal		newline

		li		$v0, 10
		syscall
#############################################################################
# Chessboard utility routines
#

##
# Get piece for column and row
# $a0 - column x
# $a1 - row y
# $a2 - chess board address
# $v0 - piece(x,y)
# If this method is altered, push t8 and t9, because they are used in the bishop check
       .text
        .globl  getpiece
getpiece:
                                # prolog        
        sub     $sp,$sp,4       #   Push return address
        sw      $ra,($sp)
        sub     $sp,$sp,4       #   Push callers frame pointer
        sw      $fp,($sp)
        sub     $fp,$sp,0       #   $fp = $sp - space_for_variables (==0)
        move    $sp,$fp         #   $sp = $fp
		
		sub		$v0,$zero,1		#	initialize the return value
		blt		$a0,0,getpieceD
		blt		$a1,0,getpieceD
		bgt		$a0,7,getpieceD	#	return -1 if out of bounds
		bgt		$a1,7,getpieceD	#	"                       "
		move	$t0, $a0		#	column x
		move	$t1, $a1		#	row y
		
		move	$t2, $a2		#	get address to the chess board
		
		li		$t3, 4
		multu	$t3, $t1		#	offset = 4*y
		mflo	$t3
		
		add		$t2, $t2, $t3	#	offset_address = board_address + 4*y
		lw		$t2, 0($t2)		#	word at offset_address

		li		$t3, 4
		multu	$t3, $t0		#	4*x
		mflo	$t3
		
		li		$t4, 28
		subu	$t3, $t4, $t3	#	28-4*x
		
		srl		$t3, $t2, $t3	#   1001xxxxxxxxxxxxxxxxxxxxxxxxxxxx becomes:
								#   00000000000000000000000000001001
		andi	$v0, $t3, 0xF		
getpieceD:              		# epilog
                                #   Return value is already in $v0        
        add     $sp,$fp,0       #   $sp = $fp + space_for_variables (==0)       
        lw      $fp,($sp)       #   Pop $fp
        add     $sp,$sp,4       #           
        lw      $ra,($sp)       #   Pop $ra
        add     $sp,$sp,4       #            
        jr      $ra             #   return to caller
##
# Get piece type for column and row
# $a0 - column x
# $a1 - row y
# $a2 - chess board location address
# $v0 - piece type
       .text
        .globl  getpiecetype
getpiecetype:
                                # prolog        
        sub     $sp,$sp,4       #   Push return address
        sw      $ra,($sp)
        sub     $sp,$sp,4       #   Push callers frame pointer
        sw      $fp,($sp)
        sub     $fp,$sp,0       #   $fp = $sp - space_for_variables (==0)
        move    $sp,$fp         #   $sp = $fp

		jal		getpiece		#	e.g. 1101
		andi	$v0, $v0, 0x7	#	101 (Queen)
		
                         		# epilog
                                #   Return value is already in $v0        
        add     $sp,$fp,0       #   $sp = $fp + space_for_variables (==0)       
        lw      $fp,($sp)       #   Pop $fp
        add     $sp,$sp,4       #           
        lw      $ra,($sp)       #   Pop $ra
        add     $sp,$sp,4       #            
        jr      $ra             #   return to caller
##
# Get piece owner for column and row
# $a0 - column x
# $a1 - row y
# $a2 - chess board location address
# $v0 - black:0, white:1
       .text
        .globl  getpieceowner
getpieceowner:
                                				# prolog        
        sub     $sp,$sp,4       				#   Push return address
        sw      $ra,($sp)
        sub     $sp,$sp,4       				#   Push callers frame pointer
        sw      $fp,($sp)
        sub     $fp,$sp,0       				#   $fp = $sp - space_for_variables (==0)
        move    $sp,$fp         				#   $sp = $fp

		jal		getpiece						#	e.g. 1101
		bgt		$v0, 0x0,getpieceowner_owned	#	check if we have an empty square
		sub		$v0, $v0, 0x1					#   if so owner is -1 (no owner)
		j		getpieceowner_end				#	or -2 for out of bounds
getpieceowner_owned:
		srl		$v0, $v0, 3						#	0001
		andi	$v0, $v0, 0x1					#	0001 (white)

getpieceowner_end:         						# epilog
                                				#   Return value is already in $v0        
        add     $sp,$fp,0       				#   $sp = $fp + space_for_variables (==0)       
        lw      $fp,($sp)       				#   Pop $fp
        add     $sp,$sp,4       				#           
        lw      $ra,($sp)       				#   Pop $ra
        add     $sp,$sp,4       				#            
        jr      $ra             				#   return to caller
##
# Draw piece for column and row
# $a0 - column x
# $a1 - row y
# $a2 - piece row
        .globl  drawpiece
drawpiece:
                                				# prolog        
        sub     $sp,$sp,4      					#   Push return address
        sw      $ra,($sp)
        sub     $sp,$sp,4       				#   Push callers frame pointer
        sw      $fp,($sp)
		sub		$sp,$sp,4						#	Push $s1
		sw		$s1,($sp)
        sub     $fp,$sp,0       				#   $fp = $sp - space_for_variables (==0)
        move    $sp,$fp         				#   $sp = $fp

		move	$t0, $a0						#	Store temporarily
		move	$t1, $a1						#	Store temporarily
		move	$t6, $a2

		add		$a0, $a0, $a1					#	Board spaces have an alternating pattern
		li		$a1, 2							#	Thus, depending on the position
		jal		mod								#	we apply the modulus to get that pattern
		move	$s1, $v0						#	Store it, because it will be used later
		beq		$s1, $zero, draw_wspace		#	This space is white
		j		draw_bspace					#	This space is black

draw_wspace:
		move	$a0, $t0
		move	$a1, $t1
		la		$a2, board
		jal		getpiece						#	Get the current piece in the space
		move	$t0, $v0
		
		beq		$t0, $zero, draw_wspace_empty			#	If it is empty, then drawempty
		li		$t1, 9
		bge		$t0, $t1, draw_wspace_wpiece				#	If it is white, then drawwhite
		
		
		j		draw_wspace_bpiece
draw_bspace:
		move	$a0, $t0
		move	$a1, $t1
		la		$a2, board
		jal		getpiece						#	Get the current piece in the space
		move	$t0, $v0
		
		beq		$t0, $zero, draw_bspace_empty			#	If it is empty, then drawempty
		li		$t1, 9
		bge		$t0, $t1, draw_bspace_wpiece				#	If it is white, then drawwhite
		j		draw_bspace_bpiece			

draw_wspace_wpiece:
li		$t1, 9
subu	$v0, $v0, $t1					#	All pieces are offset from first white pawn
la		$t1, wpawn1w
j		draw
draw_wspace_bpiece:
li		$t1, 1
subu	$v0, $v0, $t1					#	All pieces are offset from first black pawn
la		$t1, bpawn1w
j		draw
draw_bspace_wpiece:
li		$t1, 9
subu	$v0, $v0, $t1					#	All pieces are offset from first white pawn
la		$t1, wpawn1b
j		draw
draw_bspace_bpiece:
li		$t1, 1
subu	$v0, $v0, $t1					#	All pieces are offset from first black pawn
la		$t1, bpawn1b
j		draw

draw:
		li		$t2, 32							#	ASCII chars are offset by 2 bytes
		multu	$t2, $v0
		mflo	$t2
		add		$t1, $t1, $t2					#	Calculate the offset
		
		li		$t2, 8
		multu	$t6, $t2
		mflo	$t2
		add		$t1, $t1, $t2
		
		move	$a0, $t1						#	And print that piece
		jal		wrt_strz
		j		enddraw
draw_wspace_empty:
		la		$a0, wempty
		jal		wrt_strz
		j		enddraw
draw_bspace_empty:
		la		$a0, bempty
		jal		wrt_strz
		
enddraw:

                         						# epilog
                                				#   Return value is already in $v0        
        add     $sp,$fp,0       				#   $sp = $fp + space_for_variables (==0)       
        lw      $s1,($sp)       				#   Pop register $s1
        add     $sp,$sp,4       				#
        lw      $fp,($sp)       				#   Pop $fp
        add     $sp,$sp,4       				#           
        lw      $ra,($sp)       				#   Pop $ra
        add     $sp,$sp,4       				#            
        jr      $ra             				#   return to caller
###
#	Converts (column x, row y) to standard board location
#	e.g. (0,7) -> (A1)
#	$a0 : x
#	$a1 : y
       .text
        .globl  printboardloc
printboardloc:
                                # prolog        
        sub     $sp,$sp,4       #   Push return address
        sw      $ra,($sp)
        sub     $sp,$sp,4       #   Push callers frame pointer
        sw      $fp,($sp)
		sub		$sp,$sp,4
		sw		$s1,($sp)
        sub     $fp,$sp,0       #   $fp = $sp - space_for_variables (==0)
        move    $sp,$fp         #   $sp = $fp

		move	$t0, $a0		#	Store temporarily
		move	$s1, $a1		# 	Store temporarily

		li		$t2, 2
		multu	$t0, $t2		#	ASCII chars are stored offset by 2
		mflo	$t0

		la		$a0, A			#	Get the first ASCII char: A
		add		$a0, $a0, $t0	#	Offset from this char, see above declarations
		jal		wrt_strz		#	Print the string

		li		$t3, 8			#	Our origin is top left. The standard is bottom-left
		subu	$s1, $t3, $s1	#	So subtract our row from 8
		move	$a0, $s1		
		jal		wrt_int			#	And print that
		
                         		# epilog
                                #   Return value is already in $v0        
        add     $sp,$fp,0       #   $sp = $fp + space_for_variables (==0)       
		lw		$s1,($sp)
		add		$sp,$sp,4
        lw      $fp,($sp)       #   Pop $fp
        add     $sp,$sp,4       #           
        lw      $ra,($sp)       #   Pop $ra
        add     $sp,$sp,4       #            
        jr      $ra             #   return to caller
###
#	Checks if a move is valid.
#	The move is from the selected location to the current location
#	(slocx, slocy) -> (locx, locy)
       .text
        .globl  checkmove
checkmove:
                                		# prolog        
        sub     $sp,$sp,4       		#   Push return address
        sw      $ra,($sp)
        sub     $sp,$sp,4       		#   Push callers frame pointer
        sw      $fp,($sp)
		sub		$sp,$sp,4				#
		sw		$s0,($sp)
		sub		$sp,$sp,4
		sw		$s1,($sp)
		sub		$sp,$sp,4
		sw		$s2,($sp)
		sub		$sp,$sp,4
		sw		$s3,($sp)
        sub     $fp,$sp,0       		#   $fp = $sp - space_for_variables (==0)
        move    $sp,$fp        			#   $sp = $fp

		lw		$s0, slocx				# Load the selected location x
		lw		$s1, slocy				# Load the selected location y
		
		lw		$s2, locx				# Load the destination location x
		lw		$s3, locy				# Load the destination location y
		
				
		move	$a0, $s0
		move	$a1, $s1
		la		$a2, board
		jal		getpieceowner			# Get the owner of the piece to move
		move	$t4, $v0
		lw		$a0, turn
		bne		$t4, $a0, haderror		# If it is not the turn of the owner of the piece,
										# then an error has occured
		
		seq		$t0, $s0, $s2
		seq		$t1, $s1, $s3

		add		$t0, $t0, $t1			# If destination is same as source then
		beq		$t0, 2, haderror		# we have an error
		
		move	$a0, $s0
		move	$a1, $s1
		la		$a2, board
		jal		getpiece				# Get the piece to be moved
		move	$t5, $v0
		
		beq		$t5, 9, whitepawn		# If it is a white pawn go to whitepawn
		beq		$t5, 1, blackpawn		# If it is a black pawn go to blackpawn
		beq		$t5, 10, knight
		beq		$t5, 2, knight
		beq		$t5, 11, bishop
		beq		$t5, 3, bishop
		beq		$t5, 4, rook
		beq		$t5, 12, rook
		beq		$t5, 5, queen
		beq		$t5, 13, queen
		beq		$t5, 6, king
		beq		$t5, 14, king
		j		donecheck
#### Start Pawn ####
#### Start White Pawn ####		
whitepawn:
		beq		$s0, $s2, wnotcapture	# If move diagonally, then check if can capture
wtestdiag:
		move	$a2, $zero				# result = 0
		subu	$a0, $s0, $s2			# distance = slocx-locx
		li		$a1, -1					# test = -1
		seq		$a2, $a0, $a1 			# is distance == -1?
		li		$a1, 1
		beq		$a2, $a1, wtestdist		#  if (result == -1) then distance is one
				
		li		$a1, 1					# test = 1
		seq		$a2, $a0, $a2			# is distance == 1?
		
		li		$a1, 1
		beq		$a2, $a1, wtestdist		# if (result == 1) then distance is one
		j		wnotcapture
wtestdist:
		subu	$a0, $s1, $s3			# result = locy - slocy, pawn can only move one space
		
		li		$a1, 1
		beq		$a0, $a1, checkopponent	# if (result == 1) then ready to check if pawn can
										# move or capture
		j		haderror
wnotcapture:
		subu	$t5, $s1, $s3			
		ble		$t5, $zero, donecheck	
		
		beq		$s1, 6, cantaketwo		# If pawn is in row 2 it can take two steps
		bgt		$t5, 1, haderror		# If not in row 2 and takes more than 1 step, then error
		j		readytomove
#### End White Pawn ####
#### Start Black Pawn ####		
blackpawn:
		beq		$s0, $s2, bnotcapture	# If move diagonally, then error (to be modified)
btestdiag:
		move	$a2, $zero				# result = 0
		subu	$a0, $s0, $s2			# distance = slocx-locx
		li		$a1, -1					# test = -1
		seq		$a2, $a0, $a1 			# is distance == -1?
		li		$a1, 1
		beq		$a2, $a1, btestdist			#  if (result == -1) then distance is one
		
		li		$a1, 1					# test = 1
		seq		$a2, $a0, $a2			# is distance == 1?

		li		$a1, 1
		beq		$a2, $a1, btestdist			# if (result == 1) then distance is one
		j		bnotcapture
btestdist:
		subu	$a0, $s3, $s1			# result = locy - slocy

		li		$a1, 1
		beq		$a0, $a1, checkopponent

		j		haderror

bnotcapture:
		subu	$t5, $s3, $s1
		ble		$t5, $zero, donecheck

		beq		$s1, 1, cantaketwo		# If pawn is in row 7 it can take two steps
		bgt		$t5, 1, haderror		# If not in row 7 and takes more than 1 step, then error
		j		readytomove
#### End Black Pawn ####
cantaketwo:
		bgt		$t5, 2, haderror		# Pawn can't take more than 2 steps
		j		readytomove
#### End Pawn ####
#### Start Knight ####
knight:
		#A: slocx + 2, slocy + 1
		#B: slocx + 2, slocy - 1
		#C: slocx - 2, slocy + 1
		#D: slocx - 2, slocy - 1
		#E: slocx + 1, slocy + 2
		#F: slocx - 1, slocy + 2
		#G: slocx + 1, slocy - 2
		#H: slocx - 1, slocy - 2
		
		subu	$a0, $s0, $s2			# First check if tried to move knight in same column
		beq		$a0, $zero, haderror
		
		subu	$a0, $s1, $s3			# Check if tried to move knight in same row
		beq		$a0, $zero, haderror
		
		#A
		addi	$a0, $s0, 2				# a0 = slocx +2
		addi	$a1, $s1, 1				# a1 = slocy +1

		seq		$t0, $s2, $a0			# a0 == $s2? if so set t0 = 1
		seq		$t1, $s3, $a1			# a1 == $s3? if so set t1 = 1

		add		$t0, $t0, $t1			
		beq		$t0, 2, checkempty		# If both were true t0+t1 = 2

		#B
		addi	$a0, $s0, 2
		addi	$a1, $s1, -1

		seq		$t0, $s2, $a0
		seq		$t1, $s3, $a1

		add		$t0, $t0, $t1
		beq		$t0, 2, checkempty

		#C
		addi	$a0, $s0, -2
		addi	$a1, $s1, 1

		seq		$t0, $s2, $a0
		seq		$t1, $s3, $a1

		add		$t0, $t0, $t1
		beq		$t0, 2, checkempty

		#D
		addi	$a0, $s0, -2
		addi	$a1, $s1, -1

		seq		$t0, $s2, $a0
		seq		$t1, $s3, $a1

		add		$t0, $t0, $t1
		beq		$t0, 2, checkempty

		#E
		addi	$a0, $s0, 1
		addi	$a1, $s1, 2

		seq		$t0, $s2, $a0
		seq		$t1, $s3, $a1

		add		$t0, $t0, $t1
		beq		$t0, 2, checkempty

		#F
		addi	$a0, $s0, -1
		addi	$a1, $s1, 2

		seq		$t0, $s2, $a0
		seq		$t1, $s3, $a1

		add		$t0, $t0, $t1
		beq		$t0, 2, checkempty

		#G
		addi	$a0, $s0, 1
		addi	$a1, $s1, -2

		seq		$t0, $s2, $a0
		seq		$t1, $s3, $a1

		add		$t0, $t0, $t1
		beq		$t0, 2, checkempty

		#H
		addi	$a0, $s0, -1
		addi	$a1, $s1, -2

		seq		$t0, $s2, $a0
		seq		$t1, $s3, $a1

		add		$t0, $t0, $t1
		beq		$t0, 2, checkempty
		
		j		haderror
#### End Knight ####
#### Start Bishop ####
bishop:
		beq		$s0, $s2, haderror	# The source and destination cannot be in the same row
		beq		$s1, $s3, haderror  # or column, that is an illegal move for a bishop
		
		# The valid moves of a bishop can be characterized by two lines
		# y = x + b and y = -x + b where b is calculated from the current location
		# of the bishop. 
				
		# solve b in y=x+b
		sub		$t0, $s1, $s0
		# solve b in y=-x+b
		add		$t1, $s0, $s1

		# check if (locx,locy) fits in both equations
		add		$a0, $s2, $t0
		beq		$a0, $s3, check_bishop_path
		
		sub		$a0, $t1, $s2
		beq		$a0, $s3, check_bishop_path

		j		haderror
check_bishop_path:	# check which quadrant the path is in
		sub		$a0, $s2, $s0
		sub		$a1, $s3, $s1
		
		# Due to the origin of the board a few adjustments must be made
		# Looking at the board straight-on checking the top right of a bishop
		# requires incrementing x and decrementing x
		# Top-Right: 1, -1
		# Top-Left: -1, -1
		# Bottom-Right: 1, 1
		# Bottom-Left: -1, 1
		
		bgt		$a0, $zero, check_bishop_right
		j		check_bishop_left		# We've already eliminated the case where locx=slocx above
check_bishop_right:
		li		$t8, 1
		bgt		$a1, $zero, check_bishop_bottom
		j		check_bishop_top
check_bishop_left:
		li		$t8, -1
		bgt		$a1, $zero, check_bishop_bottom
		j		check_bishop_top
check_bishop_top:
		li		$t9, -1
		j		check_bishop_path_empty
check_bishop_bottom:
		li		$t9, 1
		j		check_bishop_path_empty		
check_bishop_path_empty:
		move	$s6, $s0	# Prepare the temporary variables
		move	$s7, $s1	# that will be inc/decremented
							# t2 : x value, t3 : y value
		sub		$s4, $s2, $t8 # We only want to check spaces before the destination
		sub		$s5, $s3, $t9
		
		seq		$t4, $s6, $s4	# If we're only one space away just check
		seq		$t5, $s7, $s5	# destination space
		
		add		$t4, $t4, $t5		# If we have then t4+t5=2
		beq		$t4, 2, checkempty
check_bishop_loop:
		add		$s6, $s6, $t8	# Increment by quadrant offset
		add		$s7, $s7, $t9
		
		# Check if the location is empty
		move	$a0, $s6
		move	$a1, $s7
		la		$a2, board
		jal		getpiece
		bne		$v0, $zero, haderror
		
		seq		$t4, $s6, $s4	# Check if we've reached the location yet
		seq		$t5, $s7, $s5
		
		add		$t4, $t4, $t5		# If we have then t4+t5=2
		bne		$t4, 2, check_bishop_loop	# If not then continue looping
		
		j		checkempty
#### End Bishop ####
#### Start Rook ####
rook:
		seq		$t0, $s0, $s2	# The source and destination must be in the same row
		seq		$t1, $s1, $s3  # or column
		
		add		$t0, $t0, $t1
		beq		$t0, $zero, haderror
		
		# The valid moves of a rook can be characterized by two lines
		# y = slocy and x = slocx
		
		beq		$s3, $s1, check_rook_lr
		beq		$s2, $s0, check_rook_ud

		j		haderror
check_rook_lr:
		sub		$t0, $s2, $s0
		bgt		$t0, $zero, check_rook_right
		j		check_rook_left
check_rook_right:
		li		$s7, 1
		j		check_rook_lr_empty
check_rook_left:
		li		$s7, -1
check_rook_lr_empty:		
		move	$s6, $s0	# Prepare the temporary variables

		sub		$s4, $s2, $s7 # We only want to check spaces before the destination
		
		beq		$s6, $s4, checkempty	# If we're only one space away just check destination space
check_rook_lr_loop:
		add		$s6, $s6, $s7	# Increment by quadrant offset
		
		# Check if the location is empty
		move	$a0, $s6
		move	$a1, $s2
		la		$a2, board
		jal		getpiece
		bne		$v0, $zero, haderror

		bne		$s6, $s4, check_rook_lr_loop
		
		j		checkempty
check_rook_ud:
		sub		$t0, $s3, $s1
		blt		$t0, $zero, check_rook_up
		j		check_rook_down
check_rook_up:
		li		$s7, -1
		j		check_rook_ud_empty
check_rook_down:
		li		$s7, 1
check_rook_ud_empty:
		move	$s6, $s1	# Prepare the temporary variables

		sub		$s4, $s3, $s7 # We only want to check spaces before the destination
		
		beq		$s6, $s4, checkempty	# If we're only one space away just check destination space
check_rook_ud_loop:
		add		$s6, $s6, $s7	# Increment by quadrant offset
		
		# Check if the location is empty
		move	$a0, $s2
		move	$a1, $s6
		la		$a2, board
		jal		getpiece
		bne		$v0, $zero, haderror

		bne		$s6, $s4, check_rook_ud_loop
		
		j		checkempty
#### End Rook ####
#### Start Queen ####
queen:
		seq		$t0, $s0, $s2  # If the source and destination are in the same row
		seq		$t1, $s1, $s3  # or column, then the queen is moving like a queen_uplr
		
		add		$t0, $t0, $t1
		bgt		$t0, $zero, queen_uplr
		
		# Otherwise queen is moving like a bishop
		
		# The valid moves of a bishop can be characterized by two lines
		# y = x + b and y = -x + b where b is calculated from the current location
		# of the bishop. 
				
		# solve b in y=x+b
		sub		$t0, $s1, $s0
		# solve b in y=-x+b
		add		$t1, $s0, $s1

		# check if (locx,locy) fits in both equations
		add		$a0, $s2, $t0
		beq		$a0, $s3, check_queen_diag_path
		
		sub		$a0, $t1, $s2
		beq		$a0, $s3, check_queen_diag_path

		j		haderror
check_queen_diag_path:	# check which quadrant the path is in
		sub		$a0, $s2, $s0
		sub		$a1, $s3, $s1
		
		# Due to the origin of the board a few adjustments must be made
		# Looking at the board straight-on checking the top right of a queen_diag
		# requires incrementing x and decrementing x
		# Top-Right: 1, -1
		# Top-Left: -1, -1
		# Bottom-Right: 1, 1
		# Bottom-Left: -1, 1
		
		bgt		$a0, $zero, check_queen_diag_right
		j		check_queen_diag_left		# We've already eliminated the case where locx=slocx above
check_queen_diag_right:
		li		$t8, 1
		bgt		$a1, $zero, check_queen_diag_bottom
		j		check_queen_diag_top
check_queen_diag_left:
		li		$t8, -1
		bgt		$a1, $zero, check_queen_diag_bottom
		j		check_queen_diag_top
check_queen_diag_top:
		li		$t9, -1
		j		check_queen_diag_path_empty
check_queen_diag_bottom:
		li		$t9, 1
		j		check_queen_diag_path_empty		
check_queen_diag_path_empty:
		move	$s6, $s0	# Prepare the temporary variables
		move	$s7, $s1	# that will be inc/decremented
							# t2 : x value, t3 : y value
		sub		$s4, $s2, $t8 # We only want to check spaces before the destination
		sub		$s5, $s3, $t9
		
		seq		$t4, $s6, $s4	# If we're only one space away just check
		seq		$t5, $s7, $s5	# destination space
		
		add		$t4, $t4, $t5		# If we have then t4+t5=2
		beq		$t4, 2, checkempty
check_queen_diag_loop:
		add		$s6, $s6, $t8	# Increment by quadrant offset
		add		$s7, $s7, $t9
		
		# Check if the location is empty
		move	$a0, $s6
		move	$a1, $s7
		la		$a2, board
		jal		getpiece
		bne		$v0, $zero, haderror
		
		seq		$t4, $s6, $s4	# Check if we've reached the location yet
		seq		$t5, $s7, $s5
		
		add		$t4, $t4, $t5		# If we have then t4+t5=2
		bne		$t4, 2, check_queen_diag_loop	# If not then continue looping
		
		j		checkempty
###
queen_uplr:
		seq		$t0, $s0, $s2	# The source and destination must be in the same row
		seq		$t1, $s1, $s3  # or column
		
		add		$t0, $t0, $t1
		beq		$t0, $zero, haderror
		
		# The valid moves of a queen_uplr can be characterized by two lines
		# y = slocy and x = slocx
		
		beq		$s3, $s1, check_queen_uplr_lr
		beq		$s2, $s0, check_queen_uplr_ud

		j		haderror
check_queen_uplr_lr:
		sub		$t0, $s2, $s0
		bgt		$t0, $zero, check_queen_uplr_right
		j		check_queen_uplr_left
check_queen_uplr_right:
		li		$s7, 1
		j		check_queen_uplr_lr_empty
check_queen_uplr_left:
		li		$s7, -1
check_queen_uplr_lr_empty:		
		move	$s6, $s0	# Prepare the temporary variables

		sub		$s4, $s2, $s7 # We only want to check spaces before the destination
		
		beq		$s6, $s4, checkempty	# If we're only one space away just check destination space
check_queen_uplr_lr_loop:
		add		$s6, $s6, $s7	# Increment by quadrant offset
		
		# Check if the location is empty
		move	$a0, $s6
		move	$a1, $s2
		la		$a2, board
		jal		getpiece
		bne		$v0, $zero, haderror

		bne		$s6, $s4, check_queen_uplr_lr_loop
		
		j		checkempty
check_queen_uplr_ud:
		sub		$t0, $s3, $s1
		blt		$t0, $zero, check_queen_uplr_up
		j		check_queen_uplr_down
check_queen_uplr_up:
		li		$s7, -1
		j		check_queen_uplr_ud_empty
check_queen_uplr_down:
		li		$s7, 1
check_queen_uplr_ud_empty:
		move	$s6, $s1	# Prepare the temporary variables

		sub		$s4, $s3, $s7 # We only want to check spaces before the destination
		
		beq		$s6, $s4, checkempty	# If we're only one space away just check destination space
check_queen_uplr_ud_loop:
		add		$s6, $s6, $s7	# Increment by quadrant offset
		
		# Check if the location is empty
		move	$a0, $s2
		move	$a1, $s6
		la		$a2, board
		jal		getpiece
		bne		$v0, $zero, haderror

		bne		$s6, $s4, check_queen_uplr_ud_loop
		
		j		checkempty
#### End Queen ####
#### Start King ####
king:
		# Diagonals
		# A: slocx + 1, slocy + 1
		# B: slocx + 1, slocy - 1
		# C: slocx - 1, slocy + 1
		# D: slocx - 1, slocy - 1
		
		#A
		addi	$a0, $s0, 1				# a0 = slocx +1
		addi	$a1, $s1, 1				# a1 = slocy +1

		seq		$t0, $s2, $a0			# a0 == locx? if so set t0 = 1
		seq		$t1, $s3, $a1			# a1 == locy? if so set t1 = 1

		add		$t0, $t0, $t1			
		beq		$t0, 2, checkempty		# If both were true t0+t1 = 2

		#B
		addi	$a0, $s0, 1
		addi	$a1, $s1, -1

		seq		$t0, $s2, $a0
		seq		$t1, $s3, $a1

		add		$t0, $t0, $t1
		beq		$t0, 2, checkempty

		#C
		addi	$a0, $s0, -1
		addi	$a1, $s1, 1

		seq		$t0, $s2, $a0
		seq		$t1, $s3, $a1

		add		$t0, $t0, $t1
		beq		$t0, 2, checkempty

		#D
		addi	$a0, $s0, -1
		addi	$a1, $s1, -1

		seq		$t0, $s2, $a0
		seq		$t1, $s3, $a1

		add		$t0, $t0, $t1
		beq		$t0, 2, checkempty
		
		# Up-Down-Left-Rights
		# E: slocx + 1, slocy
		# F: slocx - 1, slocy
		# G: slocx, slocy + 1
		# H: slocx, slocy - 1
		#E
		addi	$a0, $s0, 1
		add	$a1, $s1, $zero

		seq		$t0, $s2, $a0
		seq		$t1, $s3, $a1

		add		$t0, $t0, $t1
		beq		$t0, 2, checkempty

		#F
		addi	$a0, $s0, -1
		add	$a1, $s1, $zero

		seq		$t0, $s2, $a0
		seq		$t1, $s3, $a1

		add		$t0, $t0, $t1
		beq		$t0, 2, checkempty

		#G
		add	$a0, $s0, $zero
		addi	$a1, $s1, 1

		seq		$t0, $s2, $a0
		seq		$t1, $s3, $a1

		add		$t0, $t0, $t1
		beq		$t0, 2, checkempty

		#H
		add	$a0, $s0, $zero
		addi	$a1, $s1, -1

		seq		$t0, $s2, $a0
		seq		$t1, $s3, $a1

		add		$t0, $t0, $t1
		beq		$t0, 2, checkempty
		
		j		haderror
#### End King ####
checkempty:
		move	$a0, $s2
		move	$a1, $s3
		la		$a2, board
		jal		getpiece
		beq		$v0, $zero, readytomove
		j		checkopponent
readytomove:
		move	$a0, $s0
		move	$a1, $s1
		la		$a2, board
		jal		getpiece				# Get the piece to be moved
		
		move	$a2, $v0
		move	$a0, $s2
		move	$a1, $s3
		la		$a3, board
		jal		setpiece				# Move the piece to the destination
		
		move	$a0, $s0
		move	$a1, $s1
		move	$a2, $zero
		la		$a3, board
		jal		setpiece				# Make the original location empty
		
		j		donecheck
checkopponent:
		move	$a0, $s2
		move	$a1, $s3
		la		$a2, board
		jal		getpiece
		beq		$v0, $zero, haderror	# If destination is occupied, we check if it's an opponent

		move	$a0, $s2
		move	$a1, $s3
		la		$a2, board
		jal		getpieceowner
		
		lw		$a2, turn
		bne		$v0, $a2, readytocapture

		j		haderror
readytocapture:
		move	$a0, $s0
		move	$a1, $s1
		la		$a2, board
		jal		getpiece				# Get the piece to be moved

		move	$a2, $v0
		move	$a0, $s2
		move	$a1, $s3
		la		$a3, board
		jal		setpiece				# Move the piece to the destination

		move	$a0, $s0
		move	$a1, $s1
		move	$a2, $zero
		la		$a3, board
		jal		setpiece				# Make the original location empty
		
		j		donecheck
donecheck:
		li		$a0, -1
		sw		$a0, slocx				# Reset selected location x
		sw		$a0, slocy				# Reset selected location y
		
		lw		$a0, turn				# Get the current turn
		nor		$a0, $a0, $a0			# 
		andi	$a0, $a0, 1				# Make it the other player's turn

		sw		$a0, turn				# Store it
		
		lw		$t0,aiopponent
		sll		$t0,$t0,1
		or		$t0,$t0,$a0
		beq		$t0,2,aimove

		j		finished

aimove:
		la		$a0,aiinform
		jal		wrt_strz
		jal		wrt_nl
		jal		printbuff
		
		la		$a0,board
		jal		ai_alpha_beta
		
		add		$a0,$v1,$zero
		la		$a1,board
		jal		ai_copy_board
		
		la		$a0,aidecision
		jal		wrt_strz
		lw		$a0,aisrcx
		lw		$a1,aisrcy
		jal		printboardloc
		la		$a0,space
		jal		wrt_strz
		la		$a0,arrow
		jal		wrt_strz
		la		$a0,space
		jal		wrt_strz
		lw		$a0,aidestx
		lw		$a1,aidesty
		jal		printboardloc
		jal		wrt_nl
		
		jal		printbuff
		
		j		donecheck

haderror:
		sw		$s0, locx				# Reset
		sw		$s1, locy				# Reset

		# Keep the piece selected, use ESC to deselect a piece
		#li		$a0, -1
		#sw		$a0, slocx				# Reset
		#sw		$a0, slocy				# Reset
		
		li		$a0, 1					
		sw		$a0, error				# Set error flag
finished:

                         				# epilog
                                		#   Return value is already in $v0        
        add     $sp,$fp,0       		#   $sp = $fp + space_for_variables (==0)
		lw		$s3,($sp)
		add		$sp,$sp,4
		lw		$s2,($sp)
		add		$sp,$sp,4
		lw		$s1,($sp)
		add		$sp,$sp,4
		lw		$s0,($sp)
		add		$sp,$sp,4
        lw      $fp,($sp)       		#   Pop $fp
        add     $sp,$sp,4       		#           
        lw      $ra,($sp)       		#   Pop $ra
        add     $sp,$sp,4       		#            
        jr      $ra             		#   return to caller
###
# 
# Set piece for ($a0, $a1) to $a2
# $a3 is address of chess board
#
       .text
        .globl  setpiece
setpiece:
                                # prolog        
        sub     $sp,$sp,4       #   Push return address
        sw      $ra,($sp)
        sub     $sp,$sp,4       #   Push callers frame pointer
        sw      $fp,($sp)
        sub     $fp,$sp,0       #   $fp = $sp - space_for_variables (==0)
        move    $sp,$fp         #   $sp = $fp

		move	$t0, $a0		#	column x
		move	$t1, $a1		#	row y
		move	$t6, $a2

		move	$t2, $a3		#	get address to the chess board

		li		$t3, 4
		multu	$t3, $t1		#	offset = 4*y
		mflo	$t3

		add		$t2, $t2, $t3	#	offset_address = board_address + 4*y
		lw		$t5, 0($t2)		#	word at offset_address

		li		$t3, 4
		multu	$t3, $t0		# 	4*x
		mflo	$t3
		
		li		$t4, 28
		subu	$t3, $t4, $t3	# 	28-4*x
		
		li		$t7, 0xF		# 	For example, make A2 a white pawn
		sll		$t7, $t7, $t3	# 	11110000000000000000000000000000
		nor		$t7, $t7, $t7	# 	00001111111111111111111111111111
		and		$t5, $t7, $t5	# 	Mask the current row, which is:
								#	00001001100100000000000000000000
								#	With:
		sll		$t3, $t6, $t3	#   10010000000000000000000000000000
								#
		or		$t5, $t3, $t5	# 	OR them together to get
		sw		$t5, 0($t2)		#	10011001100100000000000000000000
								#	
								
								
                         		# epilog
                                #   Return value is already in $v0        
        add     $sp,$fp,0       #   $sp = $fp + space_for_variables (==0)       
        lw      $fp,($sp)       #   Pop $fp
        add     $sp,$sp,4       #           
        lw      $ra,($sp)       #   Pop $ra
        add     $sp,$sp,4       #            
        jr      $ra             #   return to caller
#############################################################################
#					Artificial Intelligence Area							#
#	AI is always going to be black, and will go to a mini-max depth of 5	#
#############################################################################

###
#	Get Value of Owned Pieces from a given board
#	a0 is boards location in memory
#	a1 is the player, 0 is black 1 is white
#	v0 returns the value of the board for black
#	P:10  K:35  B:37/39	R:50  Q:90  K:0
ai_get_owned_value:
	sub $sp,$sp,4				# backup variables
	sw $ra,0($sp)				#	ra
	sub $sp,$sp,4				#	
	sw $s0,0($sp)				#	s0
	sub $sp,$sp,4				#	
	sw $s1,0($sp)				#	s1
	sub $sp,$sp,4				#	
	sw $s2,0($sp)				#	s2
	sub $sp,$sp,4				#	
	sw $s3,0($sp)				#	s3
	sub $sp,$sp,4				#	
	sw $s4,0($sp)				#	s4
	sub $sp,$sp,4				#	
	sw $s5,0($sp)				#	s5
	
	li $s3,0					# total score counter
	li $s4,0					# dual bishop counter
	li $s0,8					# for loop max value
	li $s1,0					# row loop counter
	sll $s5,$a1,3				# player mask
ai_bval_rloop:					# for loop over rows
	li $s2,0					# column loop counter
ai_bval_cloop:					# for loop over columns
	move $a2,$a0				# get the piece at the current location
	move $a0,$s2
	move $a1,$s1
	jal getpiece
	move $a0,$a2
	addi $t0,$zero,1			# black pawn
	or $t0,$t0,$s5
	bne $v0,$t0,ai_bval_k
	addi $s3,$s3,10
	j ai_bval_O
ai_bval_k:
	addi $t0,$zero,2			# black knight
	or $t0,$t0,$s5
	bne $v0,$t0,ai_bval_b
	addi $s3,$s3,35
	j ai_bval_O
ai_bval_b:
	addi $t0,$zero,3			# black bishop
	or $t0,$t0,$s5
	bne $v0,$t0,ai_bval_r
	addi $s3,$s3,37
	addi $s4,$s4,1
	bne $s4,2,ai_bval_O
	addi $s3,$s3,4
	j ai_bval_O
ai_bval_r:
	addi $t0,$zero,4			# black rook
	bne $v0,$t0,ai_bval_q
	addi $s3,$s3,50
	j ai_bval_O
ai_bval_q:
	addi $t0,$zero,5			# black queen
	or $t0,$t0,$s5
	bne $v0,$t0,ai_bval_O
	addi $s3,$s3,90
ai_bval_O:
	addi $s2,$s2,1
	or $t0,$t0,$s5
	bne $s2,$s0,ai_bval_cloop
end_ai_bval_cloop:				# end for
	addi $s1,$s1,1
	or $t0,$t0,$s5
	bne $s1,$s0,ai_bval_rloop
end_ai_bval_rloop:				# end for
	move $v0,$s3	
								# retore variables
	lw $s5,0($sp)				#	s5
	add $sp,$sp,4				#
	lw $s4,0($sp)				#	s4
	add $sp,$sp,4				#
	lw $s3,0($sp)				#	s3
	add $sp,$sp,4				#
	lw $s2,0($sp)				#	s2
	add $sp,$sp,4				#
	lw $s1,0($sp)				#	s1
	add $sp,$sp,4				#
	lw $s0,0($sp)				#	s0
	add $sp,$sp,4				#
	lw $ra,0($sp)				#	ra
	add $sp,$sp,4				#
	jr $ra						# return to the caller

###
#	Generate Moves
#	generates all legal moves for piece at (a0,a1) on board at a2
#	v0 returns as number of moves
#	v1 returns as a pointer to a list of moves
ai_gen_moves:
								# save variables
	sub		$sp,$sp,4				#	ra
	sw		$ra,0($sp)				#
	sub		$sp,$sp,4				#	s0
	sw		$s0,0($sp)				#
	sub		$sp,$sp,4				#	s1
	sw		$s1,0($sp)				#
	sub		$sp,$sp,4				#	s2
	sw		$s2,0($sp)				#
	sub		$sp,$sp,4				#	s3
	sw		$s3,0($sp)				#
	sub		$sp,$sp,4				#	s4
	sw		$s4,0($sp)				#

	add		$s0,$zero,$a0
	add 	$s1,$zero,$a1
	add 	$s2,$zero,$a2
	add 	$s3,$zero,$zero
	add 	$s4,$zero,$zero
	jal		getpiece				# v0 now has the piece value
	and		$t0,$v0,0x7				# grab the piece's type
	and		$a3,$v0,0x8
	srl		$a3,$a3,3				# pass the player to the gen
	add		$t1,$zero,1
	bne		$t0,$t1,ai_gen_mr
	jal		ai_gen_pawn
	j		ai_gen_mO
ai_gen_mr:
	add		$t1,$zero,4
	bne		$t0,$t1,ai_gen_mn
	jal		ai_gen_rook
	j		ai_gen_mO
ai_gen_mn:
	add		$t1,$zero,2
	bne		$t0,$t1,ai_gen_mb
	jal		ai_gen_knight
	j		ai_gen_mO
ai_gen_mb:
	add		$t1,$zero,3
	bne		$t0,$t1,ai_gen_mq
	jal		ai_gen_bishop
	j		ai_gen_mO
ai_gen_mq:
	add		$t1,$zero,5
	bne		$t0,$t1,ai_gen_mk
	jal		ai_gen_queen
	j		ai_gen_mO
ai_gen_mk:
	add		$t1,$zero,6
	bne		$t0,$t1,ai_gen_mO
	jal		ai_gen_king
ai_gen_mO:
	add		$v0,$zero,$s3
	add		$v1,$zero,$s4
								# restore variables
	lw	$s4,0($sp)				#	s4
	add	$sp,$sp,4				#
	lw	$s3,0($sp)				#	s3
	add	$sp,$sp,4				#
	lw	$s2,0($sp)				#	s2
	add	$sp,$sp,4				#
	lw	$s1,0($sp)				#	s1
	add	$sp,$sp,4				#
	lw	$s0,0($sp)				#	s0
	add	$sp,$sp,4				#
	lw	$ra,0($sp)				#	ra
	add	$sp,$sp,4				#
	jr $ra

###
ai_gen_pawn:
	sub		$sp,$sp,4
	sw		$ra,0($sp)

	bne 	$a3,$zero,ai_gen_pw	# check if piece is black or white
	sub		$a0,$s0,1
	add		$a1,$s1,1
	add		$a2,$zero,$s2
	jal 	getpieceowner
	bne		$v0,0x1,ai_gen_pbd
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_pbd
	add		$s3,$s3,1
	sub		$sp,$sp,8
	sub		$t0,$s0,1
	add		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_pbd:
	add		$a0,$s0,1			# check the diagonal right for capture
	add		$a1,$s1,1
	add		$a2,$zero,$s2
	jal		getpieceowner		# get the piece, if it is >7 it is a white piece
	bne		$v0,0x1,ai_gen_pbm
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_pbm
	add		$s3,$s3,1			# add one since we can take it
	sub		$sp,$sp,8
	add		$t0,$s0,1			# check the diagonal right for capture
	add		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_pbm:
	bne		$s1,1,ai_gen_pbs	# check if we can jump two
	add		$a1,$s1,2			# check if square is blocked
	add		$a0,$zero,$s0
	add		$a2,$zero,$s2
	jal		getpiece
	bne		$v0,$zero,ai_gen_pbs
	add		$s3,$s3,1			# if not we can move there, incr count
	sub		$sp,$sp,8
	add		$t0,$s0,$zero
	add		$t1,$s1,2			
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_pbs:						# check if we can move one space ahead
	add		$a1,$s1,1
	add		$a0,$zero,$s0
	add		$a2,$zero,$s2
	jal		getpiece
	bne		$v0,$zero,ai_gen_palloc
	add		$s3,$s3,1
	sub		$sp,$sp,8
	add		$t0,$s0,$zero
	add		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)
	j		ai_gen_palloc

ai_gen_pw:
	sub		$a0,$s0,1
	sub		$a1,$s1,1
	add		$a2,$zero,$s2
	jal 	getpieceowner
	bne		$v0,$zero,ai_gen_pwd
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_pwd
	add		$s3,$s3,1
	sub		$sp,$sp,8
	sub		$t0,$s0,1
	sub		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_pwd:
	add		$a0,$s0,1			# check the diagonal right for capture
	sub		$a1,$s1,1
	add		$a2,$zero,$s2
	jal		getpieceowner		# get the piece, if it is >7 it is a white piece
	bne		$v0,$zero,ai_gen_pwm
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_pwm
	add		$s3,$s3,1			# add one since we can take it
	sub		$sp,$sp,8
	add		$t0,$s0,1			# check the diagonal right for capture
	sub		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_pwm:
	bne		$s1,6,ai_gen_pws		# check if we can jump two
	sub		$a1,$s1,2			# check if square is blocked
	add		$a0,$zero,$s0
	add		$a2,$zero,$s2
	jal		getpiece
	bne		$v0,$zero,ai_gen_pws
	add		$s3,$s3,1			# if not we can move there, incr count
	sub		$sp,$sp,8
	sub		$t1,$s1,2			# check if square is blocked
	add		$t0,$zero,$s0
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_pws:						# check if we can move one space ahead
	sub		$a1,$s1,1
	add		$a0,$zero,$s0
	add		$a2,$zero,$s2
	jal		getpiece
	bne		$v0,$zero,ai_gen_palloc
	add		$s3,$s3,1
	sub		$sp,$sp,8
	sub		$t1,$s1,1
	add		$t0,$zero,$s0
	sw		$t0,0($sp)
	sw		$t1,4($sp)

ai_gen_palloc:
	beq		$s3,$zero,ai_gen_pawnO
	add		$t0,$zero,8
	mult	$s3,$t0				# get a block of memory for our moves
	mflo	$a0
	add		$v0,$zero,9			
	syscall
	add		$s4,$zero,$v0		# save this for return later
	add		$t0,$zero,$v0		
	add		$t3,$zero,$zero
ai_gen_pbuild:
	lw		$t2,0($sp)				# grab the y coordinate from the stack
	add		$sp,$sp,4
	lw		$t1,0($sp)				# grab the x coordinate from the stack
	add		$sp,$sp,4
	sw		$t1,0($t0)				# put the x coordinate into the return vector
	add		$t0,$t0,4
	sw		$t2,0($t0)				# put the y coordinate into the return vector
	add		$t0,$t0,4
	add		$t3,$t3,1
	bne		$t3,$s3,ai_gen_pbuild
ai_gen_pawnO:
	lw	$ra,0($sp)				
	add	$sp,$sp,4				
	jr $ra

### player a3's rook at (s0,s1) on board at s2 in memory, return s3 moves in s4
ai_gen_rook:
	sub		$sp,$sp,4
	sw		$ra,0($sp)
	sub		$sp,$sp,4
	sw		$s5,0($sp)
	sub		$sp,$sp,4
	sw		$s6,0($sp)
	sub		$sp,$sp,4
	sw		$s7,0($sp)
	
	add		$s3,$zero,$zero
	add		$s4,$zero,$zero
	xor		$s5,$a3,0x1			# opponent's player value is now in s5
	add		$s6,$zero,0x1			# our loop counter
	add		$s7,$zero,$zero			# our block mask, see ai_check_check for explanation
ai_gen_rloop:
	and		$t0,$s7,0x1				# check block mask to see if right is blocked
	bgt		$t0,$zero,ai_gen_ru
	add		$a0,$s0,$s6
	add		$a1,$s1,$zero
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-1,ai_gen_rradd		# possible move if blank square
	or		$s7,$s7,0x1				# else we are blocked to the right
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_ru
	beq		$v0,$s5,ai_gen_rradd	# possible move if opponent piece
	j		ai_gen_ru
ai_gen_rradd:						# here we add the right move to list of possible moves
	add		$s3,$s3,1				# increment total possible moves
	sub		$sp,$sp,8				# add the moves to the stack for vector building later
	add		$t0,$s0,$s6
	add		$t1,$s1,$zero
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_ru:
	and		$t0,$s7,0x2				# check block mask to see if up is blocked
	bgt		$t0,$zero,ai_gen_rl
	add		$a0,$s0,$zero
	sub		$a1,$s1,$s6
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-1,ai_gen_ruadd		# possible move if blank square
	or		$s7,$s7,0x2				# else we are blocked to the up
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_rl
	beq		$v0,$s5,ai_gen_ruadd	# possible move if opponent piece
	j		ai_gen_rl
ai_gen_ruadd:						# here we add the right move to list of possible moves
	add		$s3,$s3,1				# increment total possible moves
	sub		$sp,$sp,8				# add the moves to the stack for vector building later
	add		$t0,$s0,$zero
	sub		$t1,$s1,$s6
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_rl:
	and		$t0,$s7,0x4				# check block mask to see if left is blocked
	bgt		$t0,$zero,ai_gen_rd
	sub		$a0,$s0,$s6
	add		$a1,$s1,$zero
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-1,ai_gen_rladd		# possible move if blank square
	or		$s7,$s7,0x4				# else we are blocked to the left
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_rd
	beq		$v0,$s5,ai_gen_rladd	# possible move if opponent piece
	j		ai_gen_rd
ai_gen_rladd:						# here we add the right move to list of possible moves
	add		$s3,$s3,1				# increment total possible moves
	sub		$sp,$sp,8				# add the moves to the stack for vector building later
	sub		$t0,$s0,$s6
	add		$t1,$s1,$zero
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_rd:
	and		$t0,$s7,0x8				# check block mask to see if down is blocked
	bgt		$t0,$zero,ai_gen_re
	add		$a0,$s0,$zero
	add		$a1,$s1,$s6
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-1,ai_gen_rdadd		# possible move if blank square
	or		$s7,$s7,0x8				# else we are blocked to the down
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_re
	beq		$v0,$s5,ai_gen_rdadd	# possible move if opponent piece
	j		ai_gen_re
ai_gen_rdadd:						# here we add the right move to list of possible moves
	add		$s3,$s3,1				# increment total possible moves
	sub		$sp,$sp,8				# add the moves to the stack for vector building later
	add		$t0,$s0,$zero
	add		$t1,$s1,$s6
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_re:
	beq		$s7,0xF,ai_gen_rexit
	add		$s6,$s6,0x1
	ble		$s6,0x7,ai_gen_rloop
ai_gen_rexit:
	beq		$s3,$zero,ai_gen_rreturn
	li		$t0,8					# if we found some moves we ask for the memory
	mult	$s3,$t0
	mflo	$a0
	li		$v0,9
	syscall
	add		$t0,$v0,$zero			# here we copy the memory location for working
	add		$s4,$v0,$zero			# here we copy the memory location for return
	add		$s6,$zero,$zero			# and initialize our loop variable
ai_gen_rbuild:
	lw		$t2,0($sp)				# grab the y coordinate from the stack
	add		$sp,$sp,4
	lw		$t1,0($sp)				# grab the x coordinate from the stack
	add		$sp,$sp,4
	sw		$t1,0($t0)				# put the x coordinate into the return vector
	add		$t0,$t0,4
	sw		$t2,0($t0)				# put the y coordinate into the return vector
	add		$t0,$t0,4
	add		$s6,$s6,0x1
	bne		$s6,$s3,ai_gen_rbuild	# loop for number of legal moves generated
ai_gen_rreturn:
	lw		$s7,0($sp)
	add		$sp,$sp,4
	lw		$s6,0($sp)
	add		$sp,$sp,4
	lw		$s5,0($sp)
	add		$sp,$sp,4
	lw		$ra,0($sp)
	add		$sp,$sp,4
	jr $ra

### player a3's knight at (s0,s1) on board at s2 in memory, return s3 moves in s4
ai_gen_knight:
	sub		$sp,$sp,4
	sw		$ra,0($sp)
	sub		$sp,$sp,4
	sw		$s6,0($sp)
	
	add		$s3,$zero,$zero
	add		$s4,$zero,$zero
	add		$s6,$a3,$zero			# player value now in s6
ai_gen_kna:							# check move to (+1,+2)
	add		$a0,$s0,1	
	add		$a1,$s1,2
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-2,ai_gen_knb
	beq		$v0,$s6,ai_gen_knb
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_knb
	add		$s3,$s3,1				# increment move counter and add move to stack
	sub		$sp,$sp,8
	add		$t0,$s0,1	
	add		$t1,$s1,2
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_knb:							# check move to (+2,+1)
	add		$a0,$s0,2	
	add		$a1,$s1,1
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-2,ai_gen_knc
	beq		$v0,$s6,ai_gen_knc
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_knc
	add		$s3,$s3,1				# increment move counter and add move to stack
	sub		$sp,$sp,8
	add		$t0,$s0,2	
	add		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_knc:							# check move to (+1,-2)
	add		$a0,$s0,1	
	sub		$a1,$s1,2
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-2,ai_gen_knd
	beq		$v0,$s6,ai_gen_knd
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_knd
	add		$s3,$s3,1				# increment move counter and add move to stack
	sub		$sp,$sp,8
	add		$t0,$s0,1	
	sub		$t1,$s1,2
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_knd:							# check move to (+2,-1)
	add		$a0,$s0,2	
	sub		$a1,$s1,1
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-2,ai_gen_kne
	beq		$v0,$s6,ai_gen_kne
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_kne
	add		$s3,$s3,1				# increment move counter and add move to stack
	sub		$sp,$sp,8
	add		$t0,$s0,2	
	sub		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_kne:							# check move to (-1,+2)
	sub		$a0,$s0,1	
	add		$a1,$s1,2
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-2,ai_gen_knf
	beq		$v0,$s6,ai_gen_knf
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_knf
	add		$s3,$s3,1				# increment move counter and add move to stack
	sub		$sp,$sp,8
	sub		$t0,$s0,1	
	add		$t1,$s1,2
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_knf:							# check move to (-2,+1)
	sub		$a0,$s0,2	
	add		$a1,$s1,1
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-2,ai_gen_kng
	beq		$v0,$s6,ai_gen_kng
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_kng
	add		$s3,$s3,1				# increment move counter and add move to stack
	sub		$sp,$sp,8
	sub		$t0,$s0,2	
	add		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_kng:							# check move to (-1,-2)
	sub		$a0,$s0,1	
	sub		$a1,$s1,2
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-2,ai_gen_knh
	beq		$v0,$s6,ai_gen_knh
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_knh
	add		$s3,$s3,1				# increment move counter and add move to stack
	sub		$sp,$sp,8
	sub		$t0,$s0,1	
	sub		$t1,$s1,2
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_knh:							# check move to (-2,-1)
	sub		$a0,$s0,2	
	sub		$a1,$s1,1
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-2,ai_gen_knalloc
	beq		$v0,$s6,ai_gen_knalloc
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_knalloc
	add		$s3,$s3,1				# increment move counter and add move to stack
	sub		$sp,$sp,8
	sub		$t0,$s0,2	
	sub		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)

ai_gen_knalloc:	
	beq		$s3,$zero,ai_gen_knreturn
	li		$t0,8					# if we found some moves we ask for the memory
	mult	$s3,$t0
	mflo	$a0
	li		$v0,9
	syscall
	add		$t0,$v0,$zero			# here we copy the memory location for working
	add		$s4,$v0,$zero			# here we copy the memory location for return
	add		$s6,$zero,$zero			# and initialize our loop variable
ai_gen_knbuild:
	lw		$t2,0($sp)				# grab the y coordinate from the stack
	add		$sp,$sp,4
	lw		$t1,0($sp)				# grab the x coordinate from the stack
	add		$sp,$sp,4
	sw		$t1,0($t0)				# put the x coordinate into the return vector
	add		$t0,$t0,4
	sw		$t2,0($t0)				# put the y coordinate into the return vector
	add		$t0,$t0,4
	add		$s6,$s6,0x1
	bne		$s6,$s3,ai_gen_knbuild	# loop for number of legal moves generated
ai_gen_knreturn:
	lw		$s6,0($sp)
	add		$sp,$sp,4
	lw		$ra,0($sp)
	add		$sp,$sp,4
	jr $ra

### player a3's bishop at (s0,s1) on board at s2 in memory, return s3 moves in s4
ai_gen_bishop:
	sub		$sp,$sp,4
	sw		$ra,0($sp)
	sub		$sp,$sp,4
	sw		$s5,0($sp)
	sub		$sp,$sp,4
	sw		$s6,0($sp)
	sub		$sp,$sp,4
	sw		$s7,0($sp)
	
	add		$s3,$zero,$zero
	add		$s4,$zero,$zero
	xor		$s5,$a3,0x1				# opponent's player value is now in s5
	add		$s6,$zero,0x1			# our loop counter
	add		$s7,$zero,$zero			# our block mask, see ai_check_check for explanation
ai_gen_bloop:
	and		$t0,$s7,0x1				# check block mask to see if up-right is blocked
	bgt		$t0,$zero,ai_gen_bul
	add		$a0,$s0,$s6
	sub		$a1,$s1,$s6
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-1,ai_gen_buradd	# possible move if blank square
	or		$s7,$s7,0x1				# else we are blocked to the up-right
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_bul
	beq		$v0,$s5,ai_gen_buradd	# possible move if opponent piece
	j		ai_gen_bul
ai_gen_buradd:						# here we add the right move to list of possible moves
	add		$s3,$s3,1				# increment total possible moves
	sub		$sp,$sp,8				# add the moves to the stack for vector building later
	add		$t0,$s0,$s6
	sub		$t1,$s1,$s6
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_bul:
	and		$t0,$s7,0x2				# check block mask to see if up-left is blocked
	bgt		$t0,$zero,ai_gen_bdl
	sub		$a0,$s0,$s6
	sub		$a1,$s1,$s6
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-1,ai_gen_buladd	# possible move if blank square
	or		$s7,$s7,0x2				# else we are blocked to the up-left
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_bdl
	beq		$v0,$s5,ai_gen_buladd	# possible move if opponent piece
	j		ai_gen_bdl
ai_gen_buladd:						# here we add the right move to list of possible moves
	add		$s3,$s3,1				# increment total possible moves
	sub		$sp,$sp,8				# add the moves to the stack for vector building later
	sub		$t0,$s0,$s6
	sub		$t1,$s1,$s6
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_bdl:
	and		$t0,$s7,0x4				# check block mask to see if down-left is blocked
	bgt		$t0,$zero,ai_gen_bdr
	sub		$a0,$s0,$s6
	add		$a1,$s1,$s6
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-1,ai_gen_bdladd	# possible move if blank square
	or		$s7,$s7,0x4				# else we are blocked to the down-left
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_bdr
	beq		$v0,$s5,ai_gen_bdladd	# possible move if opponent piece
	j		ai_gen_bdr
ai_gen_bdladd:						# here we add the right move to list of possible moves
	add		$s3,$s3,1				# increment total possible moves
	sub		$sp,$sp,8				# add the moves to the stack for vector building later
	sub		$t0,$s0,$s6
	add		$t1,$s1,$s6
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_bdr:
	and		$t0,$s7,0x8				# check block mask to see if down-right is blocked
	bgt		$t0,$zero,ai_gen_be
	add		$a0,$s0,$s6
	add		$a1,$s1,$s6
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-1,ai_gen_bdradd	# possible move if blank square
	or		$s7,$s7,0x8				# else we are blocked to the down-right
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_be
	beq		$v0,$s5,ai_gen_bdradd	# possible move if opponent piece
	j		ai_gen_be
ai_gen_bdradd:						# here we add the right move to list of possible moves
	add		$s3,$s3,1				# increment total possible moves
	sub		$sp,$sp,8				# add the moves to the stack for vector building later
	add		$t0,$s0,$s6
	add		$t1,$s1,$s6
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_be:
	beq		$s7,0xF,ai_gen_bexit
	add		$s6,$s6,0x1
	ble		$s6,0x7,ai_gen_bloop
ai_gen_bexit:
	beq		$s3,$zero,ai_gen_breturn
	li		$t0,8					# if we found some moves we ask for the memory
	mult	$s3,$t0
	mflo	$a0
	li		$v0,9
	syscall
	add		$t0,$v0,$zero			# here we copy the memory location for working
	add		$s4,$v0,$zero			# here we copy the memory location for return
	add		$s6,$zero,$zero			# and initialize our loop variable
ai_gen_bbuild:
	lw		$t2,0($sp)				# grab the y coordinate from the stack
	add		$sp,$sp,4
	lw		$t1,0($sp)				# grab the x coordinate from the stack
	add		$sp,$sp,4
	sw		$t1,0($t0)				# put the x coordinate into the return vector
	add		$t0,$t0,4
	sw		$t2,0($t0)				# put the y coordinate into the return vector
	add		$t0,$t0,4
	add		$s6,$s6,0x1
	bne		$s6,$s3,ai_gen_bbuild	# loop for number of legal moves generated
ai_gen_breturn:
	lw		$s7,0($sp)
	add		$sp,$sp,4
	lw		$s6,0($sp)
	add		$sp,$sp,4
	lw		$s5,0($sp)
	add		$sp,$sp,4
	lw		$ra,0($sp)
	add		$sp,$sp,4
	jr $ra

### player a3's queen at (s0,s1) on board at s2 in memory, return s3 moves in s4
ai_gen_queen:
	sub		$sp,$sp,4
	sw		$ra,0($sp)
	sub		$sp,$sp,4
	sw		$s5,0($sp)
	sub		$sp,$sp,4
	sw		$s6,0($sp)
	sub		$sp,$sp,4
	sw		$s7,0($sp)
	
	add		$s3,$zero,$zero
	add		$s4,$zero,$zero
	xor		$s5,$a3,0x1				# opponent's player value is now in s5
	add		$s6,$zero,0x1			# our loop counter
	add		$s7,$zero,$zero			# our block mask, see ai_check_check for explanation
ai_gen_qloop:
####################code from rook################################################
	and		$t0,$s7,0x1				# check block mask to see if right is blocked
	bgt		$t0,$zero,ai_gen_qu
	add		$a0,$s0,$s6
	add		$a1,$s1,$zero
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-1,ai_gen_qradd		# possible move if blank square
	or		$s7,$s7,0x1				# else we are blocked to the right
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_qu
	beq		$v0,$s5,ai_gen_qradd	# possible move if opponent piece
	j		ai_gen_qu
ai_gen_qradd:						# here we add the right move to list of possible moves
	add		$s3,$s3,1				# increment total possible moves
	sub		$sp,$sp,8				# add the moves to the stack for vector building later
	add		$t0,$s0,$s6
	add		$t1,$s1,$zero
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_qu:
	and		$t0,$s7,0x2				# check block mask to see if up is blocked
	bgt		$t0,$zero,ai_gen_ql
	add		$a0,$s0,$zero
	sub		$a1,$s1,$s6
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-1,ai_gen_quadd		# possible move if blank square
	or		$s7,$s7,0x2				# else we are blocked to the up
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_ql
	beq		$v0,$s5,ai_gen_quadd	# possible move if opponent piece
	j		ai_gen_ql
ai_gen_quadd:						# here we add the right move to list of possible moves
	add		$s3,$s3,1				# increment total possible moves
	sub		$sp,$sp,8				# add the moves to the stack for vector building later
	add		$t0,$s0,$zero
	sub		$t1,$s1,$s6
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_ql:
	and		$t0,$s7,0x4				# check block mask to see if left is blocked
	bgt		$t0,$zero,ai_gen_qd
	sub		$a0,$s0,$s6
	add		$a1,$s1,$zero
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-1,ai_gen_qladd		# possible move if blank square
	or		$s7,$s7,0x4				# else we are blocked to the left
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_qd
	beq		$v0,$s5,ai_gen_qladd	# possible move if opponent piece
	j		ai_gen_qd
ai_gen_qladd:						# here we add the right move to list of possible moves
	add		$s3,$s3,1				# increment total possible moves
	sub		$sp,$sp,8				# add the moves to the stack for vector building later
	sub		$t0,$s0,$s6
	add		$t1,$s1,$zero
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_qd:
	and		$t0,$s7,0x8				# check block mask to see if down is blocked
	bgt		$t0,$zero,ai_gen_qur
	add		$a0,$s0,$zero
	add		$a1,$s1,$s6
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-1,ai_gen_qdadd		# possible move if blank square
	or		$s7,$s7,0x8				# else we are blocked to the down
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_qur
	beq		$v0,$s5,ai_gen_qdadd	# possible move if opponent piece
	j		ai_gen_qur
ai_gen_qdadd:						# here we add the right move to list of possible moves
	add		$s3,$s3,1				# increment total possible moves
	sub		$sp,$sp,8				# add the moves to the stack for vector building later
	add		$t0,$s0,$zero
	add		$t1,$s1,$s6
	sw		$t0,0($sp)
	sw		$t1,4($sp)
####################code from bishop###############################################
ai_gen_qur:
	and		$t0,$s7,0x10			# check block mask to see if up-right is blocked
	bgt		$t0,$zero,ai_gen_qul
	add		$a0,$s0,$s6
	sub		$a1,$s1,$s6
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-1,ai_gen_quradd	# possible move if blank square
	or		$s7,$s7,0x10			# else we are blocked to the up-right
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_qul
	beq		$v0,$s5,ai_gen_quradd	# possible move if opponent piece
	j		ai_gen_qul
ai_gen_quradd:						# here we add the right move to list of possible moves
	add		$s3,$s3,1				# increment total possible moves
	sub		$sp,$sp,8				# add the moves to the stack for vector building later
	add		$t0,$s0,$s6
	sub		$t1,$s1,$s6
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_qul:
	and		$t0,$s7,0x20			# check block mask to see if up-left is blocked
	bgt		$t0,$zero,ai_gen_qdl
	sub		$a0,$s0,$s6
	sub		$a1,$s1,$s6
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-1,ai_gen_quladd	# possible move if blank square
	or		$s7,$s7,0x20			# else we are blocked to the up-left
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_qdl
	beq		$v0,$s5,ai_gen_quladd	# possible move if opponent piece
	j		ai_gen_qdl
ai_gen_quladd:						# here we add the right move to list of possible moves
	add		$s3,$s3,1				# increment total possible moves
	sub		$sp,$sp,8				# add the moves to the stack for vector building later
	sub		$t0,$s0,$s6
	sub		$t1,$s1,$s6
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_qdl:
	and		$t0,$s7,0x40			# check block mask to see if down-left is blocked
	bgt		$t0,$zero,ai_gen_qdr
	sub		$a0,$s0,$s6
	add		$a1,$s1,$s6
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-1,ai_gen_qdladd	# possible move if blank square
	or		$s7,$s7,0x40			# else we are blocked to the down-left
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_qdr
	beq		$v0,$s5,ai_gen_qdladd	# possible move if opponent piece
	j		ai_gen_qdr
ai_gen_qdladd:						# here we add the right move to list of possible moves
	add		$s3,$s3,1				# increment total possible moves
	sub		$sp,$sp,8				# add the moves to the stack for vector building later
	sub		$t0,$s0,$s6
	add		$t1,$s1,$s6
	sw		$t0,0($sp)
	sw		$t1,4($sp)
ai_gen_qdr:
	and		$t0,$s7,0x80			# check block mask to see if down-right is blocked
	bgt		$t0,$zero,ai_gen_qe
	add		$a0,$s0,$s6
	add		$a1,$s1,$s6
	add		$a2,$s2,$zero
	jal		getpieceowner
	beq		$v0,-1,ai_gen_qdradd	# possible move if blank square
	or		$s7,$s7,0x80			# else we are blocked to the down-right
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_qe
	beq		$v0,$s5,ai_gen_qdradd	# possible move if opponent piece
	j		ai_gen_qe
ai_gen_qdradd:						# here we add the right move to list of possible moves
	add		$s3,$s3,1				# increment total possible moves
	sub		$sp,$sp,8				# add the moves to the stack for vector building later
	add		$t0,$s0,$s6
	add		$t1,$s1,$s6
	sw		$t0,0($sp)
	sw		$t1,4($sp)
####################end external code###############################################
ai_gen_qe:
	beq		$s7,0xFF,ai_gen_qexit
	add		$s6,$s6,0x1
	ble		$s6,0x7,ai_gen_qloop
ai_gen_qexit:
	beq		$s3,$zero,ai_gen_qreturn
	li		$t0,8					# if we found some moves we ask for the memory
	mult	$s3,$t0
	mflo	$a0
	li		$v0,9
	syscall
	add		$t0,$v0,$zero			# here we copy the memory location for working
	add		$s4,$v0,$zero			# here we copy the memory location for return
	add		$s6,$zero,$zero			# and initialize our loop variable
ai_gen_qbuild:
	lw		$t2,0($sp)				# grab the y coordinate from the stack
	add		$sp,$sp,4
	lw		$t1,0($sp)				# grab the x coordinate from the stack
	add		$sp,$sp,4
	sw		$t1,0($t0)				# put the x coordinate into the return vector
	add		$t0,$t0,4
	sw		$t2,0($t0)				# put the y coordinate into the return vector
	add		$t0,$t0,4
	add		$s6,$s6,0x1
	bne		$s6,$s3,ai_gen_qbuild	# loop for number of legal moves generated
ai_gen_qreturn:
	lw		$s7,0($sp)
	add		$sp,$sp,4
	lw		$s6,0($sp)
	add		$sp,$sp,4
	lw		$s5,0($sp)
	add		$sp,$sp,4
	lw		$ra,0($sp)
	add		$sp,$sp,4
	jr $ra

### player a3's king at (s0,s1) on board at s2 in memory, return s3 moves in s4
ai_gen_king:
	sub		$sp,$sp,4
	sw		$ra,0($sp)
	sub		$sp,$sp,4
	sw		$s5,0($sp)
	sub		$sp,$sp,4
	sw		$s6,0($sp)
	
	add		$s6,$a3,$zero			# copy player value to s6
	add		$a0,$s2,$zero
	jal		ai_new_board
	add		$s5,$v0,$zero			# create a copy of the board for testing
	bne 	$a3,$zero,ai_gen_kw		# check if piece is black or white
ai_gen_kbr:
	add		$a0,$s0,1
	add		$a1,$s1,$zero
	add		$a2,$s2,$zero
	jal		getpieceowner			# get the piece to the right of the king
	beq		$v0,-2,ai_gen_kbur		# next direction if out of bounds
	beq		$v0,$zero,ai_gen_kbur	# next direction if one of our own
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_kbur
	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	add		$a2,$zero,$zero
	add		$a3,$s5,$zero
	jal		setpiece				# set kings old space to a blank
	add		$a0,$s0,1
	add		$a1,$s1,$zero
	add		$a2,$zero,0x6
	add		$a3,$s5,$zero
	jal		setpiece				# set kings new space to king
	add		$a0,$s6,$zero			
	add		$a1,$s5,$zero	
	jal		ai_check_check			# check if this puts him in check
	bne		$v0,$zero,ai_gen_kbur	# if it does jump to next location
	add		$s3,$s3,1				# increment legal move counter
	sub		$sp,$sp,8				# make space on stack
	add		$t0,$s0,1				
	add		$t1,$s1,$zero
	sw		$t0,0($sp)
	sw		$t1,4($sp)				# add this move to the stack
ai_gen_kbur:
	add		$a0,$s2,$zero
	add		$a1,$s5,$zero
	jal		ai_copy_board			# reset our working board for next check
	add		$a0,$s0,1
	sub		$a1,$s1,1
	add		$a2,$s2,$zero
	jal		getpieceowner			# get the piece to the up-right of the king
	beq		$v0,-2,ai_gen_kbu		# next direction if out of bounds
	beq		$v0,$zero,ai_gen_kbu	# next direction if one of our own
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_kbu
	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	add		$a2,$zero,$zero
	add		$a3,$s5,$zero
	jal		setpiece				# set kings old space to a blank
	add		$a0,$s0,1
	sub		$a1,$s1,1
	add		$a2,$zero,0x6
	add		$a3,$s5,$zero
	jal		setpiece				# set kings new space to king
	add		$a0,$s6,$zero			
	add		$a1,$s5,$zero	
	jal		ai_check_check			# check if this puts him in check
	bne		$v0,$zero,ai_gen_kbu	# if it does jump to next location
	add		$s3,$s3,1				# increment legal move counter
	sub		$sp,$sp,8				# make space on stack
	add		$t0,$s0,1				
	sub		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)				# add this move to the stack
ai_gen_kbu:
	add		$a0,$s2,$zero
	add		$a1,$s5,$zero
	jal		ai_copy_board			# reset our working board for next check
	add		$a0,$s0,$zero
	sub		$a1,$s1,1
	add		$a2,$s2,$zero
	jal		getpieceowner			# get the piece to the up of the king
	beq		$v0,-2,ai_gen_kbul		# next direction if out of bounds
	beq		$v0,$zero,ai_gen_kbul	# next direction if one of our own
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_kbul
	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	add		$a2,$zero,$zero
	add		$a3,$s5,$zero
	jal		setpiece				# set kings old space to a blank
	add		$a0,$s0,$zero
	sub		$a1,$s1,1
	add		$a2,$zero,0x6
	add		$a3,$s5,$zero
	jal		setpiece				# set kings new space to king
	add		$a0,$s6,$zero			
	add		$a1,$s5,$zero	
	jal		ai_check_check			# check if this puts him in check
	bne		$v0,$zero,ai_gen_kbul	# if it does jump to next location
	add		$s3,$s3,1				# increment legal move counter
	sub		$sp,$sp,8				# make space on stack
	add		$t0,$s0,$zero				
	sub		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)				# add this move to the stack
ai_gen_kbul:
	add		$a0,$s2,$zero
	add		$a1,$s5,$zero
	jal		ai_copy_board			# reset our working board for next check
	sub		$a0,$s0,1
	sub		$a1,$s1,1
	add		$a2,$s2,$zero
	jal		getpieceowner			# get the piece to the up-left of the king
	beq		$v0,-2,ai_gen_kbl		# next direction if out of bounds
	beq		$v0,$zero,ai_gen_kbl	# next direction if one of our own
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_kbl
	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	add		$a2,$zero,$zero
	add		$a3,$s5,$zero
	jal		setpiece				# set kings old space to a blank
	sub		$a0,$s0,1
	sub		$a1,$s1,1
	add		$a2,$zero,0x6
	add		$a3,$s5,$zero
	jal		setpiece				# set kings new space to king
	add		$a0,$s6,$zero			
	add		$a1,$s5,$zero	
	jal		ai_check_check			# check if this puts him in check
	bne		$v0,$zero,ai_gen_kbl	# if it does jump to next location
	add		$s3,$s3,1				# increment legal move counter
	sub		$sp,$sp,8				# make space on stack
	sub		$t0,$s0,1				
	sub		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)				# add this move to the stack
ai_gen_kbl:
	add		$a0,$s2,$zero
	add		$a1,$s5,$zero
	jal		ai_copy_board			# reset our working board for next check
	sub		$a0,$s0,1
	add		$a1,$s1,$zero
	add		$a2,$s2,$zero
	jal		getpieceowner			# get the piece to the left of the king
	beq		$v0,-2,ai_gen_kbdl		# next direction if out of bounds
	beq		$v0,$zero,ai_gen_kbdl	# next direction if one of our own
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_kbdl
	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	add		$a2,$zero,$zero
	add		$a3,$s5,$zero
	jal		setpiece				# set kings old space to a blank
	sub		$a0,$s0,1
	add		$a1,$s1,$zero
	add		$a2,$zero,0x6
	add		$a3,$s5,$zero
	jal		setpiece				# set kings new space to king
	add		$a0,$s6,$zero			
	add		$a1,$s5,$zero	
	jal		ai_check_check			# check if this puts him in check
	bne		$v0,$zero,ai_gen_kbdl	# if it does jump to next location
	add		$s3,$s3,1				# increment legal move counter
	sub		$sp,$sp,8				# make space on stack
	sub		$t0,$s0,1				
	add		$t1,$s1,$zero
	sw		$t0,0($sp)
	sw		$t1,4($sp)				# add this move to the stack
ai_gen_kbdl:
	add		$a0,$s2,$zero
	add		$a1,$s5,$zero
	jal		ai_copy_board			# reset our working board for next check
	sub		$a0,$s0,1
	add		$a1,$s1,1
	add		$a2,$s2,$zero
	jal		getpieceowner			# get the piece to the up-right of the king
	beq		$v0,-2,ai_gen_kbd		# next direction if out of bounds
	beq		$v0,$zero,ai_gen_kbd	# next direction if one of our own
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_kbd
	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	add		$a2,$zero,$zero
	add		$a3,$s5,$zero
	jal		setpiece				# set kings old space to a blank
	sub		$a0,$s0,1
	add		$a1,$s1,1
	add		$a2,$zero,0x6
	add		$a3,$s5,$zero
	jal		setpiece				# set kings new space to king
	add		$a0,$s6,$zero			
	add		$a1,$s5,$zero	
	jal		ai_check_check			# check if this puts him in check
	bne		$v0,$zero,ai_gen_kbd	# if it does jump to next location
	add		$s3,$s3,1				# increment legal move counter
	sub		$sp,$sp,8				# make space on stack
	sub		$t0,$s0,1				
	add		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)				# add this move to the stack
ai_gen_kbd:
	add		$a0,$s2,$zero
	add		$a1,$s5,$zero
	jal		ai_copy_board			# reset our working board for next check
	add		$a0,$s0,$zero
	add		$a1,$s1,1
	add		$a2,$s2,$zero
	jal		getpieceowner			# get the piece to the up-right of the king
	beq		$v0,-2,ai_gen_kbdr		# next direction if out of bounds
	beq		$v0,$zero,ai_gen_kbdr	# next direction if one of our own
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_kbdr
	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	add		$a2,$zero,$zero
	add		$a3,$s5,$zero
	jal		setpiece				# set kings old space to a blank
	add		$a0,$s0,$zero
	add		$a1,$s1,1
	add		$a2,$zero,0x6
	add		$a3,$s5,$zero
	jal		setpiece				# set kings new space to king
	add		$a0,$s6,$zero			
	add		$a1,$s5,$zero	
	jal		ai_check_check			# check if this puts him in check
	bne		$v0,$zero,ai_gen_kbdr	# if it does jump to next location
	add		$s3,$s3,1				# increment legal move counter
	sub		$sp,$sp,8				# make space on stack
	add		$t0,$s0,$zero				
	add		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)				# add this move to the stack
ai_gen_kbdr:
	add		$a0,$s2,$zero
	add		$a1,$s5,$zero
	jal		ai_copy_board			# reset our working board for next check
	add		$a0,$s0,1
	add		$a1,$s1,1
	add		$a2,$s2,$zero
	jal		getpieceowner			# get the piece to the up-right of the king
	beq		$v0,-2,ai_gen_kalloc	# next direction if out of bounds
	beq		$v0,$zero,ai_gen_kalloc	# next direction if one of our own
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_kalloc
	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	add		$a2,$zero,$zero
	add		$a3,$s5,$zero
	jal		setpiece				# set kings old space to a blank
	add		$a0,$s0,1
	add		$a1,$s1,1
	add		$a2,$zero,0x6
	add		$a3,$s5,$zero
	jal		setpiece				# set kings new space to king
	add		$a0,$s6,$zero			
	add		$a1,$s5,$zero	
	jal		ai_check_check			# check if this puts him in check
	bne		$v0,$zero,ai_gen_kalloc	# if it does jump to next location
	add		$s3,$s3,1				# increment legal move counter
	sub		$sp,$sp,8				# make space on stack
	add		$t0,$s0,1				
	add		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)				# add this move to the stack
	j		ai_gen_kalloc

ai_gen_kw:
ai_gen_kwr:
	add		$a0,$s0,1
	add		$a1,$s1,$zero
	add		$a2,$s2,$zero
	jal		getpieceowner			# get the piece to the right of the king
	beq		$v0,-2,ai_gen_kwur		# next direction if out of bounds
	beq		$v0,0x1,ai_gen_kwur		# next direction if one of our own
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_kwur
	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	add		$a2,$zero,$zero
	add		$a3,$s5,$zero
	jal		setpiece				# set kings old space to a blank
	add		$a0,$s0,1
	add		$a1,$s1,$zero
	add		$a2,$zero,0xE
	add		$a3,$s5,$zero
	jal		setpiece				# set kings new space to king
	add		$a0,$s6,1
	add		$a1,$s5,$zero	
	jal		ai_check_check			# check if this puts him in check
	bne		$v0,$zero,ai_gen_kwur	# if it does jump to next location
	add		$s3,$s3,1				# increment legal move counter
	sub		$sp,$sp,8				# make space on stack
	add		$t0,$s0,1				
	add		$t1,$s1,$zero
	sw		$t0,0($sp)
	sw		$t1,4($sp)				# add this move to the stack
ai_gen_kwur:
	add		$a0,$s2,$zero
	add		$a1,$s5,$zero
	jal		ai_copy_board			# reset our working board for next check
	add		$a0,$s0,1
	sub		$a1,$s1,1
	add		$a2,$s2,$zero
	jal		getpieceowner			# get the piece to the up-right of the king
	beq		$v0,-2,ai_gen_kwu		# next direction if out of bounds
	beq		$v0,0x1,ai_gen_kwu		# next direction if one of our own
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_kwu
	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	add		$a2,$zero,$zero
	add		$a3,$s5,$zero
	jal		setpiece				# set kings old space to a blank
	add		$a0,$s0,1
	sub		$a1,$s1,1
	add		$a2,$zero,0xE
	add		$a3,$s5,$zero
	jal		setpiece				# set kings new space to king
	add		$a0,$s6,1
	add		$a1,$s5,$zero	
	jal		ai_check_check			# check if this puts him in check
	bne		$v0,$zero,ai_gen_kwu	# if it does jump to next location
	add		$s3,$s3,1				# increment legal move counter
	sub		$sp,$sp,8				# make space on stack
	add		$t0,$s0,1				
	sub		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)				# add this move to the stack
ai_gen_kwu:
	add		$a0,$s2,$zero
	add		$a1,$s5,$zero
	jal		ai_copy_board			# reset our working board for next check
	add		$a0,$s0,$zero
	sub		$a1,$s1,1
	add		$a2,$s2,$zero
	jal		getpieceowner			# get the piece to the up of the king
	beq		$v0,-2,ai_gen_kwul		# next direction if out of bounds
	beq		$v0,1,ai_gen_kwul	# next direction if one of our own
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_kwul
	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	add		$a2,$zero,$zero
	add		$a3,$s5,$zero
	jal		setpiece				# set kings old space to a blank
	add		$a0,$s0,$zero
	sub		$a1,$s1,1
	add		$a2,$zero,0xE
	add		$a3,$s5,$zero
	jal		setpiece				# set kings new space to king
	add		$a0,$s6,1
	add		$a1,$s5,$zero	
	jal		ai_check_check			# check if this puts him in check
	bne		$v0,$zero,ai_gen_kwul	# if it does jump to next location
	add		$s3,$s3,1				# increment legal move counter
	sub		$sp,$sp,8				# make space on stack
	add		$t0,$s0,$zero				
	sub		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)				# add this move to the stack
ai_gen_kwul:
	add		$a0,$s2,$zero
	add		$a1,$s5,$zero
	jal		ai_copy_board			# reset our working board for next check
	sub		$a0,$s0,1
	sub		$a1,$s1,1
	add		$a2,$s2,$zero
	jal		getpieceowner			# get the piece to the up-left of the king
	beq		$v0,-2,ai_gen_kwl		# next direction if out of bounds
	beq		$v0,1,ai_gen_kwl	# next direction if one of our own
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_kwl
	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	add		$a2,$zero,$zero
	add		$a3,$s5,$zero
	jal		setpiece				# set kings old space to a blank
	sub		$a0,$s0,1
	sub		$a1,$s1,1
	add		$a2,$zero,0xE
	add		$a3,$s5,$zero
	jal		setpiece				# set kings new space to king
	add		$a0,$s6,1
	add		$a1,$s5,$zero	
	jal		ai_check_check			# check if this puts him in check
	bne		$v0,$zero,ai_gen_kwl	# if it does jump to next location
	add		$s3,$s3,1				# increment legal move counter
	sub		$sp,$sp,8				# make space on stack
	sub		$t0,$s0,1				
	sub		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)				# add this move to the stack
ai_gen_kwl:
	add		$a0,$s2,$zero
	add		$a1,$s5,$zero
	jal		ai_copy_board			# reset our working board for next check
	sub		$a0,$s0,1
	add		$a1,$s1,$zero
	add		$a2,$s2,$zero
	jal		getpieceowner			# get the piece to the left of the king
	beq		$v0,-2,ai_gen_kwdl		# next direction if out of bounds
	beq		$v0,1,ai_gen_kwdl	# next direction if one of our own
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_kwdl
	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	add		$a2,$zero,$zero
	add		$a3,$s5,$zero
	jal		setpiece				# set kings old space to a blank
	sub		$a0,$s0,1
	add		$a1,$s1,$zero
	add		$a2,$zero,0xE
	add		$a3,$s5,$zero
	jal		setpiece				# set kings new space to king
	add		$a0,$s6,1
	add		$a1,$s5,$zero	
	jal		ai_check_check			# check if this puts him in check
	bne		$v0,$zero,ai_gen_kwdl	# if it does jump to next location
	add		$s3,$s3,1				# increment legal move counter
	sub		$sp,$sp,8				# make space on stack
	sub		$t0,$s0,1				
	add		$t1,$s1,$zero
	sw		$t0,0($sp)
	sw		$t1,4($sp)				# add this move to the stack
ai_gen_kwdl:
	add		$a0,$s2,$zero
	add		$a1,$s5,$zero
	jal		ai_copy_board			# reset our working board for next check
	sub		$a0,$s0,1
	add		$a1,$s1,1
	add		$a2,$s2,$zero
	jal		getpieceowner			# get the piece to the up-right of the king
	beq		$v0,-2,ai_gen_kwd		# next direction if out of bounds
	beq		$v0,1,ai_gen_kwd	# next direction if one of our own
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_kwd
	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	add		$a2,$zero,$zero
	add		$a3,$s5,$zero
	jal		setpiece				# set kings old space to a blank
	sub		$a0,$s0,1
	add		$a1,$s1,1
	add		$a2,$zero,0xE
	add		$a3,$s5,$zero
	jal		setpiece				# set kings new space to king
	add		$a0,$s6,1
	add		$a1,$s5,$zero	
	jal		ai_check_check			# check if this puts him in check
	bne		$v0,$zero,ai_gen_kwd	# if it does jump to next location
	add		$s3,$s3,1				# increment legal move counter
	sub		$sp,$sp,8				# make space on stack
	sub		$t0,$s0,1				
	add		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)				# add this move to the stack
ai_gen_kwd:
	add		$a0,$s2,$zero
	add		$a1,$s5,$zero
	jal		ai_copy_board			# reset our working board for next check
	add		$a0,$s0,$zero
	add		$a1,$s1,1
	add		$a2,$s2,$zero
	jal		getpieceowner			# get the piece to the up-right of the king
	beq		$v0,-2,ai_gen_kwdr		# next direction if out of bounds
	beq		$v0,1,ai_gen_kwdr	# next direction if one of our own
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_kwdr
	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	add		$a2,$zero,$zero
	add		$a3,$s5,$zero
	jal		setpiece				# set kings old space to a blank
	add		$a0,$s0,$zero
	add		$a1,$s1,1
	add		$a2,$zero,0xE
	add		$a3,$s5,$zero
	jal		setpiece				# set kings new space to king
	add		$a0,$s6,1
	add		$a1,$s5,$zero	
	jal		ai_check_check			# check if this puts him in check
	bne		$v0,$zero,ai_gen_kwdr	# if it does jump to next location
	add		$s3,$s3,1				# increment legal move counter
	sub		$sp,$sp,8				# make space on stack
	add		$t0,$s0,$zero				
	add		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)				# add this move to the stack
ai_gen_kwdr:
	add		$a0,$s2,$zero
	add		$a1,$s5,$zero
	jal		ai_copy_board			# reset our working board for next check
	add		$a0,$s0,1
	add		$a1,$s1,1
	add		$a2,$s2,$zero
	jal		getpieceowner			# get the piece to the up-right of the king
	beq		$v0,-2,ai_gen_kalloc	# next direction if out of bounds
	beq		$v0,1,ai_gen_kalloc	# next direction if one of our own
	and		$t0,$v0,0x7
	beq		$t0,6,ai_gen_kalloc
	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	add		$a2,$zero,$zero
	add		$a3,$s5,$zero
	jal		setpiece				# set kings old space to a blank
	add		$a0,$s0,1
	add		$a1,$s1,1
	add		$a2,$zero,0xE
	add		$a3,$s5,$zero
	jal		setpiece				# set kings new space to king
	add		$a0,$s6,1
	add		$a1,$s5,$zero	
	jal		ai_check_check			# check if this puts him in check
	bne		$v0,$zero,ai_gen_kalloc	# if it does jump to next location
	add		$s3,$s3,1				# increment legal move counter
	sub		$sp,$sp,8				# make space on stack
	add		$t0,$s0,1				
	add		$t1,$s1,1
	sw		$t0,0($sp)
	sw		$t1,4($sp)				# add this move to the stack

ai_gen_kalloc:
	beq		$s3,$zero,ai_gen_kingO	# if we found moves alloc the necessary space
	li		$t0,8
	mult	$s3,$t0
	mflo	$a0
	li		$v0,9
	syscall
	add		$t0,$v0,$zero
	add		$t3,$s3,$zero
ai_gen_kloop:
	lw		$t2,0($sp)				# grab y coord from stack
	add		$sp,$sp,4				
	lw		$t1,0($sp)				# grab x coord from stack
	add		$sp,$sp,4
	sw		$t1,0($t0)				# put x coord into return vector
	add		$t0,$t0,4
	sw		$t2,0($t0)				# put y coord into return vector
	add		$t0,$t0,4
	sub		$t3,$t3,1				
	bne		$t3,$zero,ai_gen_kloop	# loop for the number of legal moves
	add		$s4,$v0,$zero
ai_gen_kingO:
	lw		$s6,0($sp)
	add		$sp,$sp,4
	lw		$s5,0($sp)
	add		$sp,$sp,4
	lw		$ra,0($sp)
	add		$sp,$sp,4
	jr $ra

###
#	Check-Check
#	umm...given a board and a player checks if they are checked
#	a0 is player
#	a1 is the board location in memory
#	v0 returns 1 if in checkmate, 0 if not
ai_check_check:
	sub 	$sp,$sp,4				# save variables
	sw		$ra,0($sp)
	sub 	$sp,$sp,4
	sw		$s0,0($sp)
	sub 	$sp,$sp,4
	sw		$s1,0($sp)
	sub 	$sp,$sp,4
	sw		$s2,0($sp)
	sub 	$sp,$sp,4
	sw		$s3,0($sp)
	sub 	$sp,$sp,4
	sw		$s4,0($sp)
	sub 	$sp,$sp,4
	sw		$s5,0($sp)
	sub 	$sp,$sp,4
	sw		$s6,0($sp)
	
	move	$s0,$a0					# copy arguments to safe place
	move	$s1,$a1
	sll		$t0,$a0,3
	li		$s4,6
	or		$s4,$s4,$t0				# s4 now hold the king value for the player
	li		$s2,0				
ai_cc_rloop:						# loop over board to find king
	li		$s3,0
ai_cc_cloop:
	move	$a0,$s3
	move	$a1,$s2
	move	$a2,$s1
	jal		getpiece
	beq		$v0,$s4,ai_cc_eloop		# if we found the king, jump out
	add		$s3,$s3,1
	bne		$s3,8,ai_cc_cloop		# end column for
	add		$s2,$s2,1
	bne		$s2,8,ai_cc_rloop		# end row for
ai_cc_eloop:						# at king in s4 is at point (s3,s2)
	li		$s4,1
	xori	$s5,$s0,0x1
	sll		$s5,$s5,3
	or		$s5,$s5,2				# s5 now has value for enemy knight
	add		$a0,$s3,1				# check for knight at (+1,+2)
	add		$a1,$s2,2				# yes, I know this sucks, is hackish
	add		$a2,$s1,0				# I just don't care at this point
	jal 	getpiece
	beq		$v0,$s5,ai_cc_end
	add		$a0,$s3,2				# check for knight at (+2,+1)
	add		$a1,$s2,1
	add		$a2,$s1,0
	jal 	getpiece
	beq		$v0,$s5,ai_cc_end
	add		$a0,$s3,1				# check for knight at (+1,-2)
	sub		$a1,$s2,2
	add		$a2,$s1,0
	jal 	getpiece
	beq		$v0,$s5,ai_cc_end
	add		$a0,$s3,2				# check for knight at (+2,-1)
	sub		$a1,$s2,1
	add		$a2,$s1,0
	jal 	getpiece
	beq		$v0,$s5,ai_cc_end
	sub		$a0,$s3,1				# check for knight at (-1,+2)
	add		$a1,$s2,2
	add		$a2,$s1,0
	jal 	getpiece
	beq		$v0,$s5,ai_cc_end
	sub		$a0,$s3,2				# check for knight at (-2,+1)
	add		$a1,$s2,1
	add		$a2,$s1,0
	jal 	getpiece
	beq		$v0,$s5,ai_cc_end
	sub		$a0,$s3,1				# check for knight at (-1,-2)
	sub		$a1,$s2,2
	add		$a2,$s1,0
	jal 	getpiece
	beq		$v0,$s5,ai_cc_end
	sub		$a0,$s3,2				# check for knight at (-2,-1)
	sub		$a1,$s2,1
	add		$a2,$s1,0
	jal 	getpiece
	beq		$v0,$s5,ai_cc_end		# end knight checking

# this loops out in layers checking for check on king
# it uses a mask to represent which directions the
# king is blocked from attack, from a piece or board edge
	li		$s5,1					# out loop counter
	li		$s6,0					# our blocking mask
ai_cc_kloop:
	and		$t0,$s6,0x1				# check block mask to see if right is already blocked
	bgt		$t0,$zero,ai_cc_ur		# if it is the jump to up-right check
	add		$a0,$s3,$s5				# check to the right
	add		$a1,$s2,$zero
	add		$a2,$s1,$zero
	jal 	getpiece
	beq		$v0,$zero,ai_cc_ur		# if it is a blank spot
	xor		$t0,$s0,0x1				# get opponent in t0
	sll		$t1,$t0,3
	or		$t1,$t1,0x4				
	beq		$v0,$t1,ai_cc_end		# if it is opponent rook then we are in check
	sll		$t1,$t0,3
	or		$t1,$t1,0x5				
	beq		$v0,$t1,ai_cc_end		# if it is opponent queen then we are in check
	or		$s6,$s6,0x1				# else this attack vector is blocked

ai_cc_ur:							# check up-right
	and 	$t0,$s6,2				# check block mask to see if up-right is already blocked
	bgt 	$t0,$zero,ai_cc_u		# if it is then jump to next check
	add		$a0,$s3,$s5				# check to the up-right
	sub		$a1,$s2,$s5
	add		$a2,$s1,$zero
	jal		getpiece
	beq		$v0,$zero,ai_cc_u		# if it is a blank spot skip to next check
	xor		$t0,$s0,0x1				# get opponent in t0
	sll		$t1,$t0,3
	or		$t1,$t1,0x5				
	beq		$v0,$t1,ai_cc_end		# if it is opponent queen then we are in check
	sll		$t1,$t0,3
	or		$t1,$t1,0x3				
	beq		$v0,$t1,ai_cc_end		# if it is opponent bishop then we are in check
	sll		$t1,$s0,0x3				# |player|000|
	or		$t1,$t1,$s5				# |player|layer|
	sll		$t1,$t1,0x4				# |player|layer|0000|
	or		$t1,$t1,$v0				# get a string with=|player|layer|piece|
	beq		$t1,0x91,ai_cc_end		# check for |1|001|0001|=white,layer 1,black pawn
	or		$s6,$s6,0x2				# else this attack vector is blocked by something

ai_cc_u:
	and		$t0,$s6,4				# check block mask to see if up-right is already blocked
	bgt		$t0,$zero,ai_cc_ul		# if it is then jump to next check
	add		$a0,$s3,$zero			# check to the up
	sub		$a1,$s2,$s5
	add		$a2,$s1,$zero
	jal		getpiece
	beq		$v0,$zero,ai_cc_ul		# if it is a blank spot
	xor		$t0,$s0,0x1				# get opponent in t0
	sll		$t1,$t0,3
	or		$t1,$t1,0x4				
	beq		$v0,$t1,ai_cc_end		# if it is opponent rook then we are in check
	sll		$t1,$t0,3
	or		$t1,$t1,0x5				
	beq		$v0,$t1,ai_cc_end		# if it is opponent queen then we are in check
	or		$s6,$s6,0x4				# else this attack vector is blocked

ai_cc_ul:
	and		$t0,$s6,8				# check block mask to see if up-left is already blocked
	bgt		$t0,$zero,ai_cc_l		# if it is then jump to next check
	sub		$a0,$s3,$s5				# check to the up-left
	sub		$a1,$s2,$s5
	add		$a2,$s1,$zero
	jal		getpiece
	beq		$v0,$zero,ai_cc_l		# if it is a blank spot
	xor		$t0,$s0,0x1				# get opponent in t0
	sll		$t1,$t0,3
	or		$t1,$t1,0x5				
	beq		$v0,$t1,ai_cc_end		# if it is opponent queen then we are in check
	sll		$t1,$t0,3
	or		$t1,$t1,0x3				
	beq		$v0,$t1,ai_cc_end		# if it is opponent bishop then we are in check
	sll		$t1,$s0,0x3				# |player|000|
	or		$t1,$t1,$s5				# |player|layer|
	sll		$t1,$t1,0x4				# |player|layer|0000|
	or		$t1,$t1,$v0				# get a string with=|player|layer|piece|
	beq		$t1,0x91,ai_cc_end		# check for |1|001|0001|=white,layer 1,black pawn
	or		$s6,$s6,8				# else this attack vector is blocked by something

ai_cc_l:
	and		$t0,$s6,16				# check block mask to see if up-right is already blocked
	bgt		$t0,$zero,ai_cc_dl		# if it is then jump to next check
	sub		$a0,$s3,$s5				# check to the left
	add		$a1,$s2,$zero
	add		$a2,$s1,$zero
	jal		getpiece
	beq		$v0,$zero,ai_cc_dl		# if it is a blank spot
	xor		$t0,$s0,0x1				# get opponent in t0
	sll		$t1,$t0,3
	or		$t1,$t1,0x4				
	beq		$v0,$t1,ai_cc_end		# if it is opponent rook then we are in check
	sll		$t1,$t0,3
	or		$t1,$t1,0x5				
	beq		$v0,$t1,ai_cc_end		# if it is opponent queen then we are in check
	or		$s6,$s6,0x10			# else this attack vector is blocked

ai_cc_dl:
	and		$t0,$s6,32				# check block mask to see if up-right is already blocked
	bgt		$t0,$zero,ai_cc_d		# if it is then jump to next check
	sub		$a0,$s3,$s5				# check to the down-left
	add		$a1,$s2,$s5
	add		$a2,$s1,$zero
	jal		getpiece
	beq		$v0,$zero,ai_cc_d		# if it is a blank spot
	xor		$t0,$s0,0x1				# get opponent in t0
	sll		$t1,$t0,3
	or		$t1,$t1,0x5				
	beq		$v0,$t1,ai_cc_end		# if it is opponent queen then we are in check
	sll		$t1,$t0,3
	or		$t1,$t1,0x3				
	beq		$v0,$t1,ai_cc_end		# if it is opponent bishop then we are in check
	sll		$t1,$s0,0x3				# |player|000|
	or		$t1,$t1,$s5				# |player|layer|
	sll		$t1,$t1,0x4				# |player|layer|0000|
	or		$t1,$t1,$v0				# get a string with=|player|layer|piece|
	beq		$t1,0x19,ai_cc_end		# check for |0|001|1001|=black,layer 1,white pawn
	or		$s6,$s6,0x20			# else this attack vector is blocked by something

ai_cc_d:
	and		$t0,$s6,64				# check block mask to see if up-right is already blocked
	bgt		$t0,$zero,ai_cc_dr		# if it is then jump to next check
	add		$a0,$s3,$zero			# check to the down
	add		$a1,$s2,$s5
	add		$a2,$s1,$zero
	jal		getpiece
	beq		$v0,$zero,ai_cc_dr		# if it is a blank spot
	xor		$t0,$s0,0x1				# get opponent in t0
	sll		$t1,$t0,3
	or		$t1,$t1,0x4				
	beq		$v0,$t1,ai_cc_end		# if it is opponent rook then we are in check
	sll		$t1,$t0,3
	or		$t1,$t1,0x5				
	beq		$v0,$t1,ai_cc_end		# if it is opponent queen then we are in check
	or		$s6,$s6,0x40			# else this attack vector is blocked

ai_cc_dr:
	and		$t0,$s6,128				# check block mask to see if up-right is already blocked
	bgt		$t0,$zero,ai_cc_mask	# if it is then jump to next check
	add		$a0,$s3,$s5				# check to the down-right
	add		$a1,$s2,$s5
	add		$a2,$s1,$zero
	jal		getpiece
	beq		$v0,$zero,ai_cc_mask	# if it is a blank spot
	xor		$t0,$s0,0x1				# get opponent in t0
	sll		$t1,$t0,3
	or		$t1,$t1,0x5				
	beq		$v0,$t1,ai_cc_end		# if it is opponent queen then we are in check
	sll		$t1,$t0,3
	or		$t1,$t1,0x3				
	beq		$v0,$t1,ai_cc_end		# if it is opponent bishop then we are in check
	sll		$t1,$s0,0x3				# |player|000|
	or		$t1,$t1,$s5				# |player|layer|
	sll		$t1,$t1,0x4				# |player|layer|0000|
	or		$t1,$t1,$v0				# get a string with=|player|layer|piece|
	beq		$t1,0x19,ai_cc_end		# check for |0|001|1001|=black,layer 1,white pawn
	or		$s6,$s6,0x80			# else this attack vector is blocked by something

ai_cc_mask:
	beq		$s6,255,ai_cc_ksafe
	add		$s5,$s5,1
	bne		$s5,8,ai_cc_kloop
ai_cc_ksafe:
	li		$s4,0					# we didn't find an attacker
ai_cc_end:
	move	$v0,$s4
	lw		$s6,0($sp)				# restore variables
	add		$sp,$sp,4				
	lw		$s5,0($sp)				
	add		$sp,$sp,4				
	lw		$s4,0($sp)				
	add		$sp,$sp,4				
	lw		$s3,0($sp)				
	add		$sp,$sp,4				
	lw		$s2,0($sp)				
	add		$sp,$sp,4				
	lw		$s1,0($sp)				
	add		$sp,$sp,4				
	lw		$s0,0($sp)				
	add		$sp,$sp,4				
	lw		$ra,0($sp)				
	add		$sp,$sp,4				
	jr 		$ra

###
#	Check-Checkmate
#	umm...given a board and a player checks if they are in checkmate
#	a0 is player
#	a1 is the board location
#	v0 returns 1 if in checkmate, 0 if not
ai_check_checkmate:
	sub 	$sp,$sp,4
	sw		$ra,0($sp)
	sub 	$sp,$sp,4
	sw		$s0,0($sp)
	sub 	$sp,$sp,4
	sw		$s1,0($sp)
	sub 	$sp,$sp,4
	sw		$s2,0($sp)
	sub 	$sp,$sp,4
	sw		$s3,0($sp)
	sub 	$sp,$sp,4
	sw		$s4,0($sp)
	sub 	$sp,$sp,4
	sw		$s5,0($sp)
	sub 	$sp,$sp,4
	sw		$s6,0($sp)
	sub 	$sp,$sp,4
	sw		$s7,0($sp)
	
	move	$s0,$a0					# copy arguments to safe place
	move	$s1,$a1
	add		$s5,$zero,$zero			# will hold our value to return
	jal		ai_check_check			# check if king is in check
	beq		$v0,$zero,ai_check_cmO	# if not he can't be checkmated, return
	sll		$t0,$s0,3
	li		$s4,6
	or		$s4,$s4,$t0				# s4 now hold the king value for the player
	li		$s2,0				
ai_ccm_rloop:						# loop over board to find king
	li		$s3,0
ai_ccm_cloop:
	move	$a0,$s3
	move	$a1,$s2
	move	$a2,$s1
	jal		getpiece
	beq		$v0,$s4,ai_ccm_eloop	# if we found the king, jump out
	add		$s3,$s3,1
	bne		$s3,8,ai_ccm_cloop		# end column for
	add		$s2,$s2,1
	bne		$s2,8,ai_ccm_rloop		# end row for
ai_ccm_eloop:						# at king s4 is at point (s3,s2)
	add		$a0,$s3,$zero			
	add		$a1,$s2,$zero
	add		$a2,$s1,$zero
	jal		ai_gen_moves			# see if the king has any legal moves
	bne		$v0,$zero,ai_check_cmO	# if he does, he can't be in checkmate
#
#	Begin Bug Fix - Looks to see if another piece can move to safe king
#
	add		$a0,$s1,$zero
	jal		ai_new_board
	add		$s4,$v0,$zero				# new board for evaluating moves
	add		$s2,$zero,$zero				# row loop, y-coord
ai_check_cm_rloop:
	add		$s3,$zero,$zero				# column loop, x-coord
ai_check_cm_cloop:
	#		
	# begin board loop body
	#
	add		$a0,$s3,$zero
	add		$a1,$s2,$zero
	add		$a2,$s1,$zero
	jal		getpieceowner
	bne		$v0,$s0,ai_check_cm_bloop	# go to next position if this isn't player's piece
	add		$a0,$s3,$zero
	add		$a1,$s2,$zero
	add		$a2,$s1,$zero
	jal		ai_gen_moves
	beq		$v0,$zero,ai_check_cm_bloop	# go to next position if this piece can't move
	add		$s6,$v0,$zero
	add		$s7,$v1,$zero				# store the list of possible moves in s7
ai_check_cm_mloop:						# loop over the piece's possible moves
	add		$a0,$s1,$zero
	add		$a1,$s4,$zero
	jal		ai_copy_board				# reset the board for the new move
	
	#this section will get the current piece's current possible move into board in s4
	add		$a0,$s3,$zero			
	add		$a1,$s2,$zero
	add		$a2,$zero,$zero
	add		$a3,$s4,$zero
	jal		setpiece					# set old piece to blank square
	add		$a0,$s3,$zero
	add		$a1,$s2,$zero
	add		$a2,$s1,$zero
	jal		getpiece					# get the piece we are moving
	lw		$a0,4($s7)					# load the new x-coord
	lw		$a1,0($s7)					# load the new y-coord
	add		$a2,$v0,$zero				# moving the piece we grabbed
	add		$a3,$s4,$zero
	jal		setpiece					# set the piece's new position
	add		$a0,$s0,$zero
	add		$a1,$s4,$zero
	jal		ai_check_check				# check if this saves the king
	beq		$v0,$zero,ai_check_cmO		# if there is one move that safes him, no checkmate

	add		$s7,$s7,8
	sub		$s6,$s6,1
	bne		$s6,$zero,ai_check_cm_mloop
	#
	# end board loop body
	#
ai_check_cm_bloop:
	add		$s3,$s3,1
	bne		$s3,0x8,ai_check_cm_cloop	# end of for(j=0;j<8;j++)
	add		$s2,$s2,1
	bne		$s2,0x8,ai_check_cm_rloop	# end of for(i=0;i<8;i++)
	
	add		$s5,$s5,0x1					# if he gets here, no one can save him, mated
ai_check_cm_ksafe:
#
#	End Bug Fix
#
ai_check_cmO:
	add		$v0,$s5,$zero
	lw		$s7,0($sp)
	add		$sp,$sp,4
	lw		$s6,0($sp)
	add		$sp,$sp,4
	lw		$s5,0($sp)				
	add		$sp,$sp,4				
	lw		$s4,0($sp)				
	add		$sp,$sp,4				
	lw		$s3,0($sp)				
	add		$sp,$sp,4				
	lw		$s2,0($sp)				
	add		$sp,$sp,4				
	lw		$s1,0($sp)				
	add		$sp,$sp,4				
	lw		$s0,0($sp)				
	add		$sp,$sp,4				
	lw		$ra,0($sp)				
	add		$sp,$sp,4				
	jr 		$ra

###
#	New Board
#	creates a new copy of a given board
#	a0 is location of board to be copied in memory
#	v0 returns the location of the new copy in memory
ai_new_board:
	sub		$sp,$sp,4
	sw		$ra,0($sp)
	sub		$sp,$sp,4
	sw		$s0,0($sp)
	
	add		$s0,$a0,$zero
	li		$a0,32
	li		$v0,9
	syscall							# request a new 32B board in memory
	add		$a0,$s0,$zero
	add		$a1,$v0,$zero
	jal		ai_copy_board

	lw		$s0,0($sp)
	add		$sp,$sp,4
	lw		$ra,0($sp)
	add		$sp,$sp,4
	jr		$ra

###
#	Copy Board
#	copies a given source board to a given destination
# 	assumes that the memory has already been alocated for the source
#	a0 is the location of the source board in memory
#	a1 is the location of the destination board in memory
ai_copy_board:
	sub		$sp,$sp,4
	sw		$ra,0($sp)
	
	li		$t0,0					# init loop var
	add		$t1,$a0,$zero			# init source var
	add		$t2,$a1,$zero			# init dest var
ai_copy_bloop:						# for(t0=0;t0<8;t0++)
	lw		$t3,0($t1)				# v0[t0]=a0[t0]
	sw		$t3,0($t2)
	add		$t1,$t1,4
	add		$t2,$t2,4
	add		$t0,$t0,1
	bne		$t0,8,ai_copy_bloop
	
	lw		$ra,0($sp)
	add		$sp,$sp,4
	jr		$ra

###
#	Alpha-Beta Search
#	searches possible actions for the black player on a given board
#	returns the move which is seen as the best possible given the
#	limits
#	a0 is the location of the board in memory
#	v0 returns maximum possible utility from given state for black player
#	v1 returns the location of board to use to reach this utility in memory
ai_alpha_beta:
	sub		$sp,$sp,4
	sw		$ra,0($sp)
	
	sub		$a1,$zero,0xFFFFFF
	add		$a2,$zero,0xFFFFFF
	add		$a3,$zero,$zero
	jal		ai_max_value

	lw		$ra,0($sp)
	add		$sp,$sp,4
	jr		$ra

###
#	Max-Value
#	returns the maximum possible utility for black according to 
#	the alpha-beta pruning algorithm
#	a0 is the location of the board in memory
#	a1 is the value of alpha
#	a2 is the value of beta
#	a3 is the previous depth
#	v0 returns maximum possible utility from given state for black player
#	v1 returns the location of board to use to reach this utility in memory
ai_max_value:
	sub		$sp,$sp,4
	sw		$ra,0($sp)
	sub		$sp,$sp,4
	sw		$s0,0($sp)
	sub		$sp,$sp,4
	sw		$s1,0($sp)
	sub		$sp,$sp,4
	sw		$s2,0($sp)
	sub		$sp,$sp,4
	sw		$s3,0($sp)
	sub		$sp,$sp,4
	sw		$s4,0($sp)
	sub		$sp,$sp,4
	sw		$s5,0($sp)
	sub		$sp,$sp,4
	sw		$s6,0($sp)
	sub		$sp,$sp,4
	sw		$s7,0($sp)
	
	add		$s0,$a0,$zero				# s0 = board location
	add		$s1,$a1,$zero				# s1 = alpha
	add		$s2,$a2,$zero				# s2 = beta
	sub		$sp,$sp,4					# need to store depth, but out of save variables
	sw		$a3,0($sp)					# a3 is pushed onto the stack
	
	add		$a0,$s0,$zero
	add		$a1,$a3,0x1					# pass the previous depth plus one
	jal 	ai_terminal_test
	beq		$v0,0x1,ai_max_val_terminal

	sub		$s3,$zero,0xFFFFFF			# s3 = v = -BIGNUMB
	add		$a0,$s0,$zero
	jal		ai_new_board
	add		$s7,$v0,$zero				# new board for evaluating moves
	sub		$sp,$sp,4					# create space for moves from v1 used later, on stack
	sub		$sp,$sp,4					# create space for max state pointer on stack
	add		$a0,$s0,$zero
	jal		ai_new_board
	sw		$v0,0($sp)					# put location of new board onto stack for tracking max state board
	add		$s4,$zero,$zero				# row loop, y-coord
ai_max_val_rloop:
	add		$s5,$zero,$zero				# column loop, x-coord
ai_max_val_cloop:
	#		
	# begin board loop body
	#
	add		$a0,$s5,$zero
	add		$a1,$s4,$zero
	add		$a2,$s0,$zero
	jal		getpieceowner
	bne		$v0,$zero,ai_max_val_bloop	# go to next position if this isn't black's piece
	add		$a0,$s5,$zero
	add		$a1,$s4,$zero
	jal		ai_gen_moves
	beq		$v0,$zero,ai_max_val_bloop	# go to next position if this piece can't move
	add		$s6,$v0,$zero
	sw		$v1,4($sp)					# store the list of possible moves onto stack, stack is now v1|a3|...
ai_max_val_mloop:						# loop over the piece's possible moves
	add		$a0,$s0,$zero
	add		$a1,$s7,$zero
	jal		ai_copy_board				# reset the board for the new move
	
	#this section will get the current piece's current possible move into board in s7
	add		$a0,$s5,$zero			
	add		$a1,$s4,$zero
	add		$a2,$zero,$zero
	add		$a3,$s7,$zero
	jal		setpiece					# set old piece to blank square
	add		$a0,$s5,$zero
	add		$a1,$s4,$zero
	add		$a2,$s0,$zero
	jal		getpiece					# get the piece we are moving
	lw		$t0,4($sp)					# load the list back from memory
	lw		$a0,4($t0)					# load the new x-coord
	lw		$a1,0($t0)					# load the new y-coord
	add		$a2,$v0,$zero				# moving the piece we grabbed
	add		$a3,$s7,$zero
	jal		setpiece					# set the piece's new position

	#v=max(v,min_value(s7,alpha,beta))
	add		$a0,$s7,$zero
	add		$a1,$s1,$zero
	add		$a2,$s2,$zero
	lw		$a3,8($sp)
	add		$a3,$a3,0x1
	jal		ai_min_value
	add		$a0,$v0,$zero
	add		$a1,$s3,$zero
	jal		ai_max
	
	#if max(v,min_value())!=v then the max state is the new generated one we checked
	beq		$v0,$s3,ai_max_val_bcheck
	add		$s3,$v0,$zero
	lw		$t0,8($sp)
	bne		$t0,$zero,ai_max_val_bcheck
	add		$a0,$s7,$zero
	lw		$a1,0($sp)
	jal		ai_copy_board
	sw		$s5,aisrcx
	sw		$s4,aisrcy
	lw		$t0,4($sp)
	lw		$t1,4($t0)
	lw		$t2,0($t0)
	sw		$t1,aidestx
	sw		$t2,aidesty

ai_max_val_bcheck:
	#if (v>=beta) return v as the max-value, and s7 as the state with this value
	bge		$s3,$s2,ai_max_val_betapruned
	#else alpha=max(alpha,v) and we go to next move/piece
	add		$a0,$s1,$zero
	add		$a1,$s3,$zero
	jal		ai_max
	add		$s1,$v0,$zero
	lw		$v1,4($sp)
	add		$v1,$v1,8
	sw		$v1,4($sp)
	sub		$s6,$s6,1
	bne		$s6,$zero,ai_max_val_mloop
	#
	# end board loop body
	#
ai_max_val_bloop:
	add		$s5,$s5,1
	bne		$s5,0x8,ai_max_val_cloop	# end of for(j=0;j<8;j++)
	add		$s4,$s4,1
	bne		$s4,0x8,ai_max_val_rloop	# end of for(i=0;i<8;i++)
ai_max_val_eloop:
	lw		$s7,0($sp)
	j		ai_max_val_end
ai_max_val_terminal:					# if the state is terminal return the states utility
	add		$a0,$zero,$zero
	add		$a1,$s0,$zero
	jal		ai_utility
	add		$v1,$s0,$zero
	j		ai_max_val_return
ai_max_val_betapruned:
	lw		$t0,8($sp)
	bne		$t0,$zero,ai_max_val_end
	sw		$s5,aisrcx
	sw		$s4,aisrcy
	lw		$t0,4($sp)
	lw		$t1,4($t0)
	lw		$t2,0($t0)
	sw		$t1,aidestx
	sw		$t2,aidesty
ai_max_val_end:							# return the calculated v and the last computed state					
	add		$sp,$sp,4					# free up stack space from old max stack var
	add		$sp,$sp,4					# free up stack space from old v1
	add		$v0,$s3,$zero
	add		$v1,$s7,$zero
ai_max_val_return:
	lw		$a3,0($sp)
	add		$sp,$sp,4
	lw		$s7,0($sp)
	add		$sp,$sp,4
	lw		$s6,0($sp)
	add		$sp,$sp,4
	lw		$s5,0($sp)
	add		$sp,$sp,4
	lw		$s4,0($sp)
	add		$sp,$sp,4
	lw		$s3,0($sp)
	add		$sp,$sp,4
	lw		$s2,0($sp)
	add		$sp,$sp,4
	lw		$s1,0($sp)
	add		$sp,$sp,4
	lw		$s0,0($sp)
	add		$sp,$sp,4
	lw		$ra,0($sp)
	add		$sp,$sp,4
	jr		$ra

###
#	Min-Value
#	returns the minimum possible utility for black according 
#	to the alpha-beta pruning algorithm
#	a0 is the location of the board in memory
#	a1 is the value of alpha
#	a2 is the value of beta
#	a3 is the depth of previous level
#	v0 returns the minimum possible utility for the black player from given state
#	v1 returns the location of board to use to reach this utility in memory
ai_min_value:
	sub		$sp,$sp,4
	sw		$ra,0($sp)
	sub		$sp,$sp,4
	sw		$s0,0($sp)
	sub		$sp,$sp,4
	sw		$s1,0($sp)
	sub		$sp,$sp,4
	sw		$s2,0($sp)
	sub		$sp,$sp,4
	sw		$s3,0($sp)
	sub		$sp,$sp,4
	sw		$s4,0($sp)
	sub		$sp,$sp,4
	sw		$s5,0($sp)
	sub		$sp,$sp,4
	sw		$s6,0($sp)
	sub		$sp,$sp,4
	sw		$s7,0($sp)
	
	add		$s0,$a0,$zero				# s0 = board location
	add		$s1,$a1,$zero				# s1 = alpha
	add		$s2,$a2,$zero				# s2 = beta
	sub		$sp,$sp,4					# need to store depth, but out of save variables
	sw		$a3,0($sp)					# a3 is pushed onto the stack
	
	add		$a0,$s0,$zero
	add		$a1,$a3,0x1				# this should be the current depth
	jal 	ai_terminal_test
	beq		$v0,0x1,ai_min_val_terminal

	add		$s3,$zero,0xFFFFFF			# s3 = v = BIGNUMB
	add		$a0,$s0,$zero
	jal		ai_new_board
	add		$s7,$v0,$zero				# new board for evaluating moves
	sub		$sp,$sp,4					# put away space for v1 used later, on stack
	sub		$sp,$sp,4					# create space for min state pointer on stack
	add		$a0,$s0,$zero
	jal		ai_new_board
	sw		$v0,0($sp)
	add		$s4,$zero,$zero				# row loop, y-coord
ai_min_val_rloop:
	add		$s5,$zero,$zero				# column loop, x-coord
ai_min_val_cloop:
	#		
	# begin board loop body
	#
	add		$a0,$s5,$zero
	add		$a1,$s4,$zero
	add		$a2,$s0,$zero
	jal		getpieceowner
	bne		$v0,0x1,ai_min_val_bloop	# go to next position if this isn't white's piece
	add		$a0,$s5,$zero
	add		$a1,$s4,$zero
	jal		ai_gen_moves
	beq		$v0,$zero,ai_min_val_bloop	# go to next position if this piece can't move
	add		$s6,$v0,$zero
	sw		$v1,4($sp)					# store the list of possible moves onto stack
ai_min_val_mloop:						# loop over the piece's possible moves
	add		$a0,$s0,$zero
	add		$a1,$s7,$zero
	jal		ai_copy_board				# reset the board for the new move
	
	#this section will get the current piece's current possible move into board in s7
	add		$a0,$s5,$zero			
	add		$a1,$s4,$zero
	add		$a2,$zero,$zero
	add		$a3,$s7,$zero
	jal		setpiece					# set old piece to blank square
	add		$a0,$s5,$zero
	add		$a1,$s4,$zero
	add		$a2,$s0,$zero
	jal		getpiece					# get the piece we are moving
	lw		$t0,4($sp)					# load the list back from memory
	lw		$a0,4($t0)					# load the new x-coord
	lw		$a1,0($t0)					# load the new y-coord
	add		$a2,$v0,$zero				# moving the piece we grabbed
	add		$a3,$s7,$zero
	jal		setpiece					# set the piece's new position

	#v=min(v,max_value(s7,alpha,beta))
	add		$a0,$s7,$zero
	add		$a1,$s1,$zero
	add		$a2,$s2,$zero
	lw		$a3,8($sp)
	add		$a3,$a3,0x1
	jal		ai_max_value
	add		$a0,$v0,$zero
	add		$a1,$s3,$zero
	jal		ai_min
	#if min(v,max_value())!=v then the min state is the new generated one we checked
	beq		$v0,$s3,ai_min_val_bcheck
	add		$s3,$v0,$zero
	lw		$t0,8($sp)
	bne		$t0,$zero,ai_min_val_bcheck
	add		$a0,$s7,$zero
	lw		$a1,0($sp)
	jal		ai_copy_board
	
ai_min_val_bcheck:
	#if (v<=alpha) return v as the min-value, and s7 as the state with this value
	ble		$s3,$s2,ai_min_val_end
	#else beta=min(beta,v) and we go to next move/piece
	add		$a0,$s2,$zero
	add		$a1,$s3,$zero
	jal		ai_min
	add		$s2,$v0,$zero
	lw		$v1,4($sp)
	add		$v1,$v1,8
	sw		$v1,4($sp)
	sub		$s6,$s6,1
	bne		$s6,$zero,ai_min_val_mloop
	#
	# end board loop body
	#
ai_min_val_bloop:
	add		$s5,$s5,1
	bne		$s5,0x8,ai_min_val_cloop	# end of for(j=0;j<8;j++)
	add		$s4,$s4,1
	bne		$s4,0x8,ai_min_val_rloop	# end of for(i=0;i<8;i++)
ai_min_val_eloop:
	lw		$s7,0($sp)
	j		ai_min_val_end
ai_min_val_terminal:					# if the state is terminal return the states utility
	add		$a0,$zero,$zero
	add		$a1,$s0,$zero
	jal		ai_utility
	add		$v1,$s0,$zero
	j		ai_min_val_return
ai_min_val_end:							# return the calculated v and the last computed state					
	add		$sp,$sp,4					# free up stack space from old v1
	add		$sp,$sp,4					# free up stack space from old v1
	add		$v0,$s3,$zero
	add		$v1,$s7,$zero
ai_min_val_return:
	lw		$a3,0($sp)
	add		$sp,$sp,4
	lw		$s7,0($sp)
	add		$sp,$sp,4
	lw		$s6,0($sp)
	add		$sp,$sp,4
	lw		$s5,0($sp)
	add		$sp,$sp,4
	lw		$s4,0($sp)
	add		$sp,$sp,4
	lw		$s3,0($sp)
	add		$sp,$sp,4
	lw		$s2,0($sp)
	add		$sp,$sp,4
	lw		$s1,0($sp)
	add		$sp,$sp,4
	lw		$s0,0($sp)
	add		$sp,$sp,4
	lw		$ra,0($sp)
	add		$sp,$sp,4
	jr		$ra

###
#	Terminal-Test
#	returns whether a given board state would be considered
#	terminal(ie white is checked, checkmated, tree is too deep)
#	a0 is location of board in memory
#	a1 is the current depth
#	v0 returns 1 if terminal, 0 if not terminal
ai_terminal_test:
	sub		$sp,$sp,4
	sw		$ra,0($sp)
	sub		$sp,$sp,4
	sw		$s0,0($sp)
	sub		$sp,$sp,4
	sw		$s1,0($sp)
		
	add		$v0,$zero,0x1					# check if we are too deep
	bgt		$a1,0x4,ai_terminal_test_return
	add		$s0,$a0,$zero
	add		$s1,$a1,$zero

	li		$a0,0							# check if black is in checkmate
	add		$a1,$s0,$zero
	jal		ai_check_checkmate
	bgt		$v0,$zero,ai_terminal_test_return
	beq		$s1,0x1,ai_tt_wcm

	li		$a0,0							# check if black is checked, past first move
	add		$a1,$s0,$zero
	jal		ai_check_check
	beq		$v0,$zero,ai_terminal_test_return

ai_tt_wcm:
	li		$a0,1							# check if white is in checkmate
	add		$a1,$s0,$zero
	jal		ai_check_checkmate
	bgt		$v0,$zero,ai_terminal_test_return
	
	add		$v0,$zero,$zero
ai_terminal_test_return:
	lw		$s1,0($sp)
	add		$sp,$sp,4
	lw		$s0,0($sp)
	add		$sp,$sp,4
	lw		$ra,0($sp)
	add		$sp,$sp,4
	jr		$ra

###
#	Max
#	given two numbers it returns the max of the two
#	a0 is the first number
#	a1 is the second number
#	v0 returns max(a0,a1)
ai_max:
	add		$v0,$a0,$zero
	bgt		$a0,$a1,ai_max_end
	add		$v0,$a1,$zero
ai_max_end:
	jr		$ra

###
#	Min
#	given two numbers it returns the min of the two
#	a0 is the first number
#	a1 is the second number
#	v0 returns min(a0,a1)
ai_min:
	add		$v0,$a0,$zero
	blt		$a0,$a1,ai_min_end
	add		$v0,$a1,$zero
ai_min_end:
	jr		$ra

###
#	Utility
#	returns the utility for a given player on a given board
#	a0 is the current player
#	a1 is the location of the board in memory
#	v0 returns the utility for player a0 on board a1
ai_utility:
	sub		$sp,$sp,4
	sw		$ra,0($sp)
	sub		$sp,$sp,4
	sw		$s0,0($sp)
	sub		$sp,$sp,4
	sw		$s1,0($sp)
	sub		$sp,$sp,4
	sw		$s2,0($sp)
	sub		$sp,$sp,4
	sw		$s3,0($sp)

# change this to prioritize the utility
# 1. check if self is checked, if so horrible utility and return
# 2a. check if opponent is checked,
# 2b. check if opponent is checkmated, if so awesome utility and return
# 2c. else really good utility, and continue
# 3. add to utility the value of owned pieces
# 4. subtract from utility the value of opponent owned pieces

	add		$s0,$a0,$zero					# current player = s0
	add		$s1,$a1,$zero					# current board = s1 
	xor		$s2,$s0,0x1						# opponent player = s2
	add		$s3,$zero,$zero
		
	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	jal		ai_check_check					# utility is horrible if player is checked/checkmated
	add		$t0,$zero,$zero
	sne		$t0,$v0,$zero
	bne		$t0,$zero,ai_utility_end
	sll		$t0,$t0,0x10
	sub		$s3,$s3,$t0

	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	jal		ai_check_check					# utility is awesome if opponent is checked/checkmated
	add		$t0,$zero,$zero
	sne		$t0,$v0,$zero
	beq		$t0,$zero,ai_utility_val
	sll		$t0,$t0,0x9
	add		$s3,$s3,$t0						# utility is good if opponent is checked
	add		$a0,$s0,$zero
	add		$a1,$s1,$zero
	jal		ai_check_checkmate
	add		$t0,$zero,$zero
	sne		$t0,$v0,$zero
	beq		$t0,$zero,ai_utility_val
	sll		$t0,$t0,0xD
	add		$s3,$s3,$t0						# utility is awesome if opponent is checkamted
	j		ai_utility_end

ai_utility_val:
	add		$a0,$s1,$zero
	add		$a1,$s0,$zero
	jal		ai_get_owned_value
	add		$s3,$v0,$zero					# s3=player value
	add		$a0,$s1,$zero
	add		$a1,$s2,$zero
	jal		ai_get_owned_value
	sub		$s3,$s3,$v0						# s3-=opponent value

ai_utility_end:
	add		$v0,$s3,$zero
	lw		$s3,0($sp)
	add		$sp,$sp,4
	lw		$s2,0($sp)
	add		$sp,$sp,4
	lw		$s1,0($sp)
	add		$sp,$sp,4
	lw		$s0,0($sp)
	add		$sp,$sp,4
	lw		$ra,0($sp)
	add		$sp,$sp,4
	jr		$ra
#############################################################################
	.data
other_str:
	.asciiz "Non-interrupt exception\n"
no_recv_str:
	.asciiz "Receiver not ready\n"
no_trans_str:
	.asciiz "Transmitter not ready\n"
bad_int_str:
	.asciiz "Unknown interrupt\n"
	

############################################################################################
# $a0 - string address
# $a1 - string size
       .text
        .globl  wrt_strz
wrt_strz:
                                # prolog        
        sub     $sp,$sp,4       #   Push return address
        sw      $ra,($sp)
        sub     $sp,$sp,4       #   Push callers frame pointer
        sw      $fp,($sp)
        sub     $fp,$sp,0       #   $fp = $sp - space_for_variables (==0)
        move    $sp,$fp         #   $sp = $fp

		move	$t0, $a0 		# str_addr

		lw		$t2, buff 		# buff_start

		# Write to sec*4 + off
		lw		$t3, sec
		lw		$t4, off

		li		$t6, 4
		mult	$t3, $t6 		# sec*4
		mflo	$t5
		add		$t5, $t4, $t5 	# sec*4 + off
		add		$t2, $t2, $t5 	# buff_start + sec*4 + off

		li		$t1, 0	# str_size
str_incz:		
		lb		$t5, 0($t0)		# t3 = (str_addr)

		beq		$t5, $zero, calc_sec_off		
		sb		$t5, 0($t2)		# (buff_start) = t3

		addi	$t0, $t0, 1 	# str_addr++
		addi	$t1, $t1, 1 	# str_size++
		addi	$t2, $t2, 1		# buff_start++

		bne		$t5, $zero, str_incz # if(counter != str_size): goto str_incz
calc_sec_off:		
		li		$t6, 4
		mult	$t3, $t6 		# sec*4
		mflo	$t5
		add		$t5, $t4, $t5 	# sec*4 + off

		add		$t2, $t5, $t1	# sec*4 + off + str_size

		li		$t3, 4
		div		$t2, $t3
		mflo	$t3
		mfhi	$t2

end_wrt_strz:
		sw		$t3, sec		# store sec
		sw		$t2, off		# store off

              					# epilog
                                #   Return value is already in $v0        
        add     $sp,$fp,0       #   $sp = $fp + space_for_variables (==0)       
        lw      $fp,($sp)       #   Pop $fp
        add     $sp,$sp,4       #           
        lw      $ra,($sp)       #   Pop $ra
        add     $sp,$sp,4       #            
        jr      $ra             #   return to caller

############################################################################################
        .globl  wrt_nl
wrt_nl:
                                # prolog        
        sub     $sp,$sp,4       #   Push return address
        sw      $ra,($sp)
        sub     $sp,$sp,4       #   Push callers frame pointer
        sw      $fp,($sp)
        sub     $fp,$sp,0       #   $fp = $sp - space_for_variables (==0)
        move    $sp,$fp         #   $sp = $fp

		la	$a0, nl
		jal	wrt_strz

              					# epilog
                                #   Return value is already in $v0        
        add     $sp,$fp,0       #   $sp = $fp + space_for_variables (==0)       
        lw      $fp,($sp)       #   Pop $fp
        add     $sp,$sp,4       #           
        lw      $ra,($sp)       #   Pop $ra
        add     $sp,$sp,4       #            
        jr      $ra             #   return to caller
############################################################################################	    
# $a0 - integer	
		.globl  wrt_int
wrt_int:
                                # prolog        
        sub     $sp,$sp,4       #   Push return address
        sw      $ra,($sp)
        sub     $sp,$sp,4       #   Push callers frame pointer
        sw      $fp,($sp)
		sub     $sp,$sp,4
		sw      $s0,($sp)
		sub     $sp,$sp,4
		sw      $s1,($sp)
		sub     $sp,$sp,4
		sw      $s2,($sp)
		sub     $sp,$sp,4
		sw      $s3,($sp)
        sub     $fp,$sp,0       #   $fp = $sp - space_for_variables (==0)
        move    $sp,$fp         #   $sp = $fp

		move	$s0, $a0
		li	$s1, 10
		li	$s3, 0
rev_digit_loop:
		div		$s0, $s1
		mfhi	$s2
		mflo 	$s0

		mult	$s3, $s1
		mflo	$s3
		add		$s3, $s3, $s2

		bne	$s0, $zero, rev_digit_loop

		move	$s0, $s3

		li	$a0, 4
		li	$v0, 9
		syscall
		move	$s3, $v0
		sb		$zero, 1($s3)
digit_loop:
		div		$s0, $s1
		mfhi	$s2
		mflo 	$s0

		move	$a0, $s2
		addi	$a0, $a0, 48
		sb		$a0, 0($s3)

		la	$a0, 0($s3)
		jal wrt_strz

		bne	$s0, $zero, digit_loop

              					# epilog
                                #   Return value is already in $v0        
        add     $sp,$fp,0       #   $sp = $fp + space_for_variables (==0)       
		lw		$s3,($sp)
		add		$sp,$sp,4
		lw		$s2,($sp)
		add		$sp,$sp,4
		lw		$s1,($sp)
		add		$sp,$sp,4
		lw		$s0,($sp)
		add		$sp,$sp,4
        lw      $fp,($sp)       #   Pop $fp
        add     $sp,$sp,4       #           
        lw      $ra,($sp)       #   Pop $ra
        add     $sp,$sp,4       #            
        jr      $ra             #   return to caller

############################################################################################
        .globl  printbuff
printbuff:
                                # prolog        
        sub     $sp,$sp,4       #   Push return address
        sw      $ra,($sp)
        sub     $sp,$sp,4       #   Push callers frame pointer
        sw      $fp,($sp)
        sub     $fp,$sp,0       #   $fp = $sp - space_for_variables (==0)
        move    $sp,$fp         #   $sp = $fp

		lw		$t2, buff

		# write 0x0 to sec*4 + off + 1
		lw		$t3, sec
		lw		$t4, off

		li		$t6, 4
		mult	$t3, $t6 		# sec*4
		mflo	$t5
		add		$t5, $t4, $t5 	# sec*4 + off
		add		$t2, $t2, $t5 	# buff_start + sec*4 + off
		addi	$t2, $t2, 1

		li		$t3, 0
		sb		$t3, 0($t2)

		lw		$a0, buff
		jal		printstr

		sw		$zero, sec
		sw		$zero, off

              					# epilog
                                #   Return value is already in $v0        
        add     $sp,$fp,0       #   $sp = $fp + space_for_variables (==0)       
        lw      $fp,($sp)       #   Pop $fp
        add     $sp,$sp,4       #           
        lw      $ra,($sp)       #   Pop $ra
        add     $sp,$sp,4       #            
        jr      $ra             #   return to caller
#############################################################################

